Questions on cryptography and cryptanalysis, encryption and decryption, and the making and breaking of codes and ciphers.

learn more… | top users | synonyms (2)

1
vote
1answer
21 views

Discrete Logarithm Problem

Question: Discrete Logarithm Problem: Let $g$ be a primitive root for $F_{p}$. Suppose that $x = a$ and $x = b$ are both integer solutions to the congruence $g^{x} \equiv h \pmod{p}$. Prove that $a ...
0
votes
1answer
16 views

Finding the Modular Multiplicative Inverse of a large number

I am practicing some modular arithmetic and I am trying to find the multiplicative inverse of a large number. Here is the problem: 345^-1 mod 76408 I'm not sure how to go about solving this problem. ...
1
vote
0answers
16 views

Modular Arithmetic - pairs of additive inverse pairs and multiplicative inverse pairs

I am taking a Cryptography class and we are working on modular arithmetic. I am still unsure on how to find pairs of additive inverse pairs and multiplicative inverse pairs. I've seen some videos and ...
0
votes
2answers
48 views

Understanding why the public exponent $e$ is chosen the way it is in RSA

I am trying to get a better understanding of RSA. At the moment I am unable to understand the difference between the correctly chosen value of the public exponent $e$ and other possibilities ...
1
vote
1answer
25 views

Decrypting an Affine Cipher with Modulus

I'm trying to decrypt the ciphertext vczkh which I know was encoded using an affine cipher with the equation 7x + 8(mod 26). This makes my decryption function p = (c – b) * a^-1 (mod 26) where b = 8, ...
1
vote
1answer
45 views

What books do you recommend on mathematics behind cryptography?

I am currently reading the Book Understanding Cryptography from Cristof Paar. I am enjoying the book but i don't like to scratch the surface when it comes to cryptography. I would like do dig a little ...
0
votes
1answer
30 views

Reversible modular exponent in cryptography

I know this is possible from working code, but I can't wrap my head around how. For the given equation: $b = x^p\bmod\text{public_key}$ Where $p$ is prime ($131$ in my case). How to compute a ...
0
votes
1answer
10 views

Identify encryption scheme - possibly DSA or Diffie Hellman - only client shares key

I could use a hand in identifying the encryption scheme used in this scenario. (Its from source code known to work) There is a client connecting to a server such that: ...
0
votes
0answers
27 views

Rabin cipher question

I am getting wrong answer to this question. Any one else too has solved it ? Decrypt the Ciphertext message 1819 0459 0803 that was encrypted using the Rabin Cryptosystem with b= 3 and n= 47 *59
-1
votes
0answers
30 views

How would I go about cracking a playfair cipher without knowing the key

I know that I need to analyse bigrams etc and have worked out th, he, er, in and have worked out where th and he correspond to in my grid, but now I am stumped! Can I get any advice please? I have ...
-1
votes
0answers
16 views

Epsilon Differential privacy using laplace distribution

Given Database X={x_1 ,x_2 ,...X_n} where x_i represent a bit Let f(x) = Sum x_i for 1 <= i <= n Let Y ~laplace(1/(epsilon)) I succeeded proving that Mechanisms: M1(x)= Y-f(x) and M2(x)= ...
0
votes
0answers
17 views

1-2 Oblivious Transfer and its simulation by ordinary OT

The version of 1-2 oblivious transfer mentioned in Even, Goldreich and Lempel [1985] has the provision that the receiver, Bob, can discover with probability > 1/2 if the sender, Alice, sends the same ...
0
votes
0answers
14 views

Blum Micali Algorithm Security By Seed Size

I'm coming from a computer science background, so I'm having some difficulty with these high level mathematics. With reference to the Blum Micali algorithm: (underscore represent subscript) ...
0
votes
1answer
27 views

Factors of the RSA modulus

In the article "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems", the original RSA article, it is mentioned that Miller has shown that n (the modulus) can be factored using any ...
0
votes
2answers
35 views

Find all primes different from three for which $(3|p)=1$

Find all primes different from three for which $(3|p)=1$, where $(3|p)$ denotes the Ligendre symbol.
0
votes
0answers
14 views

What's the implication of the Frobenius automorphism to DLP

Given a field, e.g. GF(p^x), does the existence of a Frobenius automorphism affect the difficulty of calculating the discrete log in that field? How about other morphisms?
3
votes
3answers
328 views

Encryption with large mods

I am studying for a cryptography final and I have come across something I can just not figure out. My math background is rather weak. This is related to RSA and concerns itself with raising numbers ...
0
votes
1answer
20 views

RSA decryption where e=3 m=12

I have a problem with RSA Decryption, if I set $n=3*11=33$ I get $\varphi(33)=20$ and e=3 the first problem is encrypting the Message 12, when I encrypt $12^3\equiv 12 (mod 33)$ meaning the the ...
0
votes
1answer
44 views

To have a career researching Cryptography is it better to do PhD in Math / Computer Science

The question is as above: To have a career researching Cryptography is it better to do PhD in Math / Computer Science? I looked through Faculty profiles for researchers working on Cryptography, some ...
1
vote
1answer
36 views

RSA Encryption (Block division)

I have a fair idea of what RSA encryption is and how to do it, but I don't quite understand the following bit given in my textbook: I have an exam tomorrow and I'm expected to encrypt a string of ...
1
vote
0answers
53 views

Does there exist some relations between Cryptography and Algebraic Topology?

We know that there are many application of Cryptography in our real life. Are there any relation between Cryptography and Algebraic Topology? If yes, please suggest me some link or books. Thanks ...
1
vote
0answers
44 views

provably secure hash function

I have the following question related to proving a hash function is secure if discrete log in group $\mathbb{G}$ is hard. The hash function (Gen,H) goes as follows: Gen: on input $1^n$, run to obtain ...
0
votes
1answer
70 views

solving mod equation

I am attempting to solve $r_1$ in this equation: $$m + xr \equiv m_1 + xr_1 \pmod q$$ This is what I derived at: $$m-m_1 + xr / x \equiv r_1 \pmod q$$ I proceed to sub these with the necessary ...
1
vote
1answer
23 views

Are bit permutations linear?

I'm trying to answer a question on cryptography. Basically, inputs and outputs (so plaintexts and ciphertexts) are from the set (say) $\{0, 1\}^{100}$. The encryption function takes inputs and splits ...
2
votes
1answer
67 views

Cryptography, discrete mathematics

I have got following example at the lecture, however we went through it quite fast. I understand the calculation of the following inverse modulo: 7 · 103 = 1 (mod 120). However here I am puzzled ...
2
votes
1answer
48 views

Textbook RSA game with one prime

Let p be a n-bits prime number, that is drawn uniformly. Let e and m uniformly drawn from Z(p-1) and Z*(p) respectively. Let y= (m^e) mod p Prove that the probability to find m while knowing only ...
3
votes
0answers
76 views

Evaluate a rational function at infinity

In the context of the Tate pairing, I would like to know that it means to `evaluate' an $\mathbb{F}_{q^k}$-rational function at $\infty$. For instance, the reduced Tate pairing is $e_n:G_1\times ...
0
votes
1answer
76 views

Use Pohlig-Hellman to solve discrete log

We have $$7^x = 166 \pmod{433}$$ I need to find $x$ using the Pohlig-Hellman algorithm.
-1
votes
1answer
30 views

NTRU cryptosystem

For the NTRU cryptosystem (as described here http://en.wikipedia.org/wiki/NTRUEncrypt), why is it really easy for Eve to decrypt if $p$ divides $q$. My answer was that when Eve sees $e(x)= ...
1
vote
2answers
34 views

Undoing anonymous donations

All the students in a class are planning to do a trip. Not all of the students can afford it, and it is considered shameful to reveal their poverty. So it is suggested that anyone can donate ...
0
votes
1answer
19 views

How is it possible to write $\text {Pr} [M = m]$ where $M$ is random variable defined over a message space $\mathcal M$ and $m \in \mathcal M$.

In cryptography we consider random variables $K, M$ and $C$ over the key space $\mathcal K$ , message space $\mathcal M$ and cipher space $\mathcal C$, respectively. I've studied discrete mathematics ...
0
votes
1answer
46 views

NTRU cryptosystem

In the NTRU cryptosystem we are dealing with convolution polynomial rings and we compute $f(x)= T(d+1,d)$ and $g(x)= T(d,d)$ but when calculating their inverse in $R_q=(Z/qZ[x] / (x^N-1))$ and ...
1
vote
0answers
38 views

Find a polynomial of degree $8$ with integer coefficients with given root

algorithm to find a polynomial $f(x)$ s.t (1) $degree(f(x))<9$ (2) Integer coefficients (3) Absolute value of coefficients $< 10^5$ (4) f(39.770525) =~ 0 about to be <<10^-10 I ...
0
votes
1answer
23 views

Why in cryptography it is common to use the SAME key for all the group?

I believe that it is safer that each member should have his or her encryption and decryption keys that no one else knows. IN this case a message $m$ is sent as $m^{e_1}$ the receiver sends $t$ back as ...
0
votes
2answers
34 views

Continuous trapdoor functions?

Every trapdoor function I've seen has been a discrete function. Do there exist continuous trapdoor functions? If so, what's an example of a continuous trapdoor function? And if not, why not?
0
votes
1answer
39 views

Cryptography question

I think this is a pohlig hellman symmetric key system working in $\mathbb{Z}/p\mathbb{Z}$ Assuming Alice and Bob both have p (a prime) and k (a key) If Alice sends $m^k$ to Bob, can Bob raise $m^k$ ...
0
votes
0answers
31 views

Could this discrete logarithm problem be proved?

Given some values $X$, $Y$, $A$, $B$ and $p$, is there a way to show that there exists (or doesn't exist) an $n$ such that $X = A^n \mod{p}$ and $Y = B^n \mod{p}$? Alternatively, are there particular ...
1
vote
4answers
122 views

Elliptic curves (sum and multiply)

I was wondering if someone could give me some resources on elliptic curve cryptography. Specifically I need to know how to do something like: $y^2=x^3-x+1$ compute $(0,1)⊕(1,1)$ or $y^2=x^3+x^2-x$ ...
0
votes
0answers
29 views

Elliptic curve cryptography order

How do I compute an order a a point P on an elliptic curve? My question is specifically in reference to the attached photo. I understand how to do part a but I am totally lost in part b. I don't know ...
1
vote
0answers
29 views

Advice needed in Cryptography

I'm currently in my undergrad studies (3rd Year in 2015) , majoring in pure mathematics and statistics. I'm thinking of pursuing cryptography for my Honours project, as its the closest thing that ...
1
vote
1answer
28 views

Modular equation with non-integer numbers?

I was reading the book Homomorphic Encryption and Applications when I saw a modular equation involvind non-integer numbers. In short, on page 59 the book define the set $y$ as $\{y_1, y_2, .., ...
1
vote
1answer
29 views

Elliptic curves: Can I replace a coordinate with any modularly equivalent number?

I have a point (x, y) in an elliptic curve group. Suppose y is negative. Can I rewrite it as a positive number if that positive number is equivalent to y (modulo the characteristic of the group)? ...
0
votes
1answer
23 views

El Gamal encryption/decryption

First of all I want to ask if I did part a correctly? Alice has two secrets, $s_1 = 55$ and $s_2 = 108$ and wants to communicate one of them to Bob without knowing which one. Alice and Bob agree to ...
0
votes
0answers
26 views

Algorithm for solving 2PLE

I have a trouble with this article which trats an attack on the Isonorphism Problem with 2 linear secrets. At the end of page 11 the author analizes the properties of a system using a certain ...
2
votes
1answer
51 views

Prove a residue matrix $A$ (with coefficients in $\mathbb Z_n)$ has an inverse if and only if $\gcd(\det A,n) = 1$

Prove a residue matrix $A$ (with coefficients in $\mathbb Z_n)$ has an inverse if and only if $\gcd(\det A,n) = 1$. I've always done matrix arithmetic in a field $\mathbb F$ and that is what ...
0
votes
1answer
21 views

Generating a quadratic polynomial in RSA (cryptosystem)

Question: Suppose that n is the product of distinct primes p and q, so n=pq Show that p and q are the roots of the quadratic equation x^2 -(n+1 -φ(n))x + n Hence if n and φ(n) are known then n can ...
2
votes
1answer
59 views

Points on elliptic curve over finite field

Find the points on the elliptic curve $y^2 = x^3 + 2x + 2$ in $\mathbb F_{17}$. Do I have to guess a first point and then use an algorithm to spit out all other points?
1
vote
0answers
31 views

RSA and El Gamal Algorithms

I have to write a short report about RSA and El Gamal algorithms in cryptography. I just need to summarize them (how one would calculate the various components, what their strengths and weaknesses ...
0
votes
1answer
23 views

What is a probability ensemble?

The definition I have says An ensemble index by I is a sequences of random variables indexed by I. Namely, any X = {X_i}_{i \in I}, where each X_i is a random variable, is an ensemble indexed by I. ...
0
votes
0answers
16 views

RSA and El Gamal

I was wondering if anyone knew where I could find some examples of encryption with El Gamal and RSA using very large primes? I wrote a code for El Gamal and RSA but I want to test it with some known ...