I am using the RSA crytposytem. I have $p$, $q$ and hence $n$ and $\phi$ however I don't understand how to get $e$ such that $gcd(e,\phi)=1$  Many thanks
122310
I'm learning RSA in one of my classes and we were given a problem:     $p = 5$, $q = 11$   I have done the following steps:     $n = 5 \cdot 11 = 55$   $\phi = (5-1)\cdot(11-1) = 40$   I know that to find $e$ we have to find an integer co-prime with $\phi$, where $\phi$ is $40$ and $\gcd(e,40) = 1$.  Is there an algorithm I can use by hand that can give me $e$? I know there can be numerous values. The method the professor has shown is to just enumerate each prime and find the first divisible into the totient $\phi$. I assume he will give us small numbers in the exam but still, doing it by trial and error can be time consuming.  I understand one can use extended Euclids algorithm to find the inverse of $e$, which I can do provided I know what $e$ is.  I just struggle with finding $e$.
14644
I've recently heard some people claiming that if the fact that P = NP is proven, most (all?) the current cryptographic algorithm considered secure like RSA will be unusable in secure systems.  My question is :  1. If P = NP is proven TODAY, will a RSA key (let say 3072 bits) be still enough to ensure a certain amount of security.  2. If not, what could we do to have at least the same amount of security (take a larger key length? a stronger algorithm?)
14976
I'm going to encrypt the characters Zhu, and decrypt them using RSA. I'm using the public key $\{e, n\}$ and private key $\{d, n\}$. The values of $e$, $d$ and $p$ I get from my textbook: $e = 17$, $d = 53$, $n = 77$.  It works fine when the number is smaller than 76, but in my example below, it doesn't work:  z = 90  h = 104  u = 107  e = 17 d = 53 n = 77  print z,h,u  c_z = z ** e % n c_h = h ** e % n c_u = u ** e % n  print c_z, c_h, c_u  p_z = c_z ** d % n p_h = c_h ** d % n p_u = c_u ** d % n  print p_z, p_h, p_u   The outputs are:  90 104 107 62 69 46 13 27 30     Do you have any idea what's going wrong?
86327
Is there an efficient way (algorihtm) to compute the solutions of the congruence $x^n\equiv a \pmod p$?   $n\in \mathbb{N}$ $a\in\mathbb{Z}_p$ $p$ is a large prime number   Note that:   By efficient I mean computationally efficient even when the given prime $p$ is appropriate for use in cryptographic protocols (hard to find discrete logarithm in $\mathbb{Z}_p$) We do not know the prime factors of $p-1$.   It’s easy to find one solution when $\gcd(n,p-1)=1$.  I think this should be as hard as finding a Discrete Logarithm or as Factoring. Any ideas ? Thank you for your time.
53376
I am looking at the following question from my undergraduate Number Theory textbook:  Show that if p,q are different odd primes, and if gcd(p,q)=1, then a$\Phi$(pq)/2 $\equiv$  $1$ mod $pq$.  So far, the approach I have taken is trying to split up a$\Phi$(pq)/2 = (a$\Phi$(p)/2)$\Phi$(q) and apply Euler's theorem but I don't think I am really getting anywhere.  Any help would be greatly appreciated, thank you!
13882
It is possible to find an efficient algorithm for constructing a provably hard to factor number $N$, together with a witness that shows that it is indeed hard to factor. EDIT, since it was not clear: I also want to be sure that even the person that constructed the number cannot factor it.  Of course, a random large enough integer is going to be hard to factor with high probability, but we might be unlucky.  There are also multi-party protocols for shared generation of RSA moduli (such as ), but I would like a non interactive technique.  Motivation: This was suggested by Poncho's answer to
22267
I am trying to make the RSA structure of Openssl manually, knowing the public key ($n$, $e$) and the  parameters $p$, $q$, $d_P$, $d_Q$, and $u = q^{-1} \mod p$.  That is, I want to get the $d$ value (private exponent) of the RSA structure by using Openssl API. If there are already any implemented functions, it would be great to me.  Bonus question: is it possible if I have $p$, $q$, $d_P$, $d_Q$ and $u$ but not the public key? I know that $n = p q$, but what about $e$?
51033
Pre-conditions:  Let the public key be $(n, e)$, and $n=pq$, which $p,q$ are large distinct primes. Let $gcd(e, (p-1)(q-1))=1$, and $d$ is the inverse of $e$ modulo $(p-1)(q-1)$.   And let $M$ be the raw message, $M &lt; pq$, and $C$ represents the encrypted message(i.e. $M^e$).    Proof:  Since $M &lt; pq$, and $p, q$ are prime, $gcd(M, pq) &gt; 1$ implies that $gcd(M, p)=p$ or $gcd(M,q)=q$, but not both.  WLOG, consider the case $gcd(M, p)=p$ and $gcd(M, q)=1$. Let $ed=1+k(p-1)(q-1)$, then we have:   $C^d \equiv (M^e)^d \equiv 0\ (\textrm{mod}\ p) \equiv M\ (\textrm{mod}\ p)$ $C^d \equiv (M^e)^d \equiv M\cdot M^{k(p-1)(q-1)} \equiv M\cdot1^{k(p-1)} \equiv M\ (\textrm{mod}\ q)$   Since $gcd(p,q)=1$, $C^d \equiv M\ (\textrm{mod}\ pq)$ by Chinese Remainder Theorem. $\mathbf{Q.E.D.}$    This is an exercise in my text book Discrete Mathematics and it's Application, Rosen, page 305, section 4.6. And I don't have the solution...
79879
I would like to factorise $496241$. I know the answer is $677 \times 733$. But I don't know how to get there.   Here is the full question:   "A message has been encoded using RSA with a modulus of $m = p q = 496241$ (with $p$ and $q$ being primes) and encoding exponent of $218821$.  You are advised that $\{13631, 142703\}$ is a valid encoding–decoding pair for the same modulus, $m$.  (a) Use this information to determine $\phi(m)$ for this modulus. (Using software to directly factorise $m$ is not a valid option for doing this part.)  (b) Verify your answer by determining the primes $p$ and $q$. Show how these combine to give both $m$ and $\phi(m)$."  I need it so I can solve (a), and it says I cannot use software to directly factorise m. So I guess pen and paper. But there are not tutorial online. Thanks
62602
My attempt was suppose $\gcd (n+5, n^2+9) = d$ where $d$ is an integer, hence $d|n+5$ and $d|n^2+9$ but I don't know how could I rearrange this to make it $1$
6364
When given $p = 5, q = 11, N = 55$ and $e = 17$, I'm trying to compute the RSA private key $d$.  I can calculate $\varphi(N) = 40$, but my lecturer then says to use the extended Euclidean algorithm to compute $d$. That's where I get stuck.    Here's my work so far:  First I use the Euclid algorithm to calculate:  40 = 2(17) + 6  17 = 2(6) + 5 6 = 1(5) + 1 = gcd   So I know the GCD is 1. Applying the 'extended' section of the algorithm:  6 = 40-2(17) 5 = 17-2(6) 1 = 6-1(5) 1 = 6-1(17-2(6)) 3(6) = 1 (17) 3(40 - 2(17)) - 1(17) 3(40) - 3(17)   I know the answer is $33$, but I have no idea how to get there using the extended Euclidean algorithm. I can't figure out why I'm getting $3(40) - 3(17)$ when I know the answer should contain $33$.
66002
How would you show that if $ac≡bc$ $\mod m$ and $\gcd(c,m)=d$, then  $a≡b$ $\mod \frac{m}{d}$?  Any help would be much appreciated!
39267
I need help finding all $n$ such that $\phi(n)=n/3$.    I understand how to do it for $n/2$ but not for $n/3$. Thank you.
17890
I saw the answer to  and it is the same problem, but i didn't get how to use the tip S.C.B gave. This was the tip: $"$First, assume that it is not $a$ primitive root $(\text{mod m})$. Then we have that there exists such $r&lt;\phi(m)$ such that $$a^r\equiv 1(\text{mod m})$$ Now use that, if $n=mk$ $$ϕ(mk)=ϕ(m)ϕ(k)\frac{d}{ϕ(d)}≥ϕ(m)ϕ(k)&gt;rϕ(k)$$ where $d=gcd(m,k)"$ and i saw the answer to this question using group theory, but i want an answer using elementary number theory, if you have a different answer, or tip, it would be good as well. What i tried was this: $n=mk$, then $$a^{\phi(n)}\equiv 1(\text{mod n})\Rightarrow a^{\phi(mk)}\equiv1(\text{mod mk}) \Rightarrow a^{\phi(mk)}\equiv1(\text{mod m})$$ But i don't know how to follow from here
4111
Given the RSA modulus $N$ the fastest method to factor it is of sub-exponent order. But, now if I know the private key $d$ of RSA, does that mean I can factor $N$ efficiently?. It intuitively seems true as I know the public/private key pair. Can someone help me to prove this?  Please provide references so that I can read further into this subject.
47293
How can I prove that if $\gcd(a,b)=1$, then $\gcd(a^2,b^2)=1$, without using prime decomposition? I should only use definition of gcd, division algorithm, Euclidean algorithm and corollaries to those. Thanks for your help!
121669
I did:  $$gcd(84,5) = \\ 84 = 5*16+4 \\ 5=4*1+1$$  $$4 = 84-5*16 \\ 1 = 5-4*1 \\ 1 = 5-(84-5*16)\\ 1 = 17*5-1*84$$  So the answer should be $1$ but it's 4, what went wrong?