Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I studied some encryption and decryption and I have found some very interesting problem to solve on the internet. I hope I am writing to right site - there are so many in StackExchange otherwise I hope some moderator will move it.

So, how to choose the appropriate public lets say (i, m) and private (j, m) keys which could be subsequently used to (de)encrypt in RSA when there are primes lets say p = 17 and q = 5?

I tried something like:

17*5=85

(17-1)*(5-1)=64

64 should be magic number but still do not know what to do next, can anyone help me here?
I would really appreciate how to choose and in which way these keys ...

share|improve this question
    
I assume you mean keys, not kies? –  orlp Jun 12 '13 at 2:13
    
Yes sorry .. Corrected –  Byakugan Jun 12 '13 at 2:20
    
I'm not entirely sure what you're asking. Your last sentence doesn't really make sense. –  Savara Jun 12 '13 at 10:03

1 Answer 1

up vote 2 down vote accepted

I assume that $m = pq$ (85) is the modulus, and the number you computed (64) is $\phi(m)$. Now we must choose the exponents ($i$ for public, $j$ for secret? , weird notation) in such a way that $ij = 1$ modulo $\phi(m)$. In fact we can work modulo 16 if we like, because that is the least common multiple of $p-1$ and $q-1$. So if we choose $i = 3$, we choose $j=11$, as $33 \equiv 1 \mod 16$. Or $i=11$, $j=3$, this is symmetrical. Or we could choose $i = 5$ and then $j=13$ works, or vice versa again.

Then encryption of a number smaller than $m$ is exponentiation to the power $i$, modulo $m$ and decryption is exponentiation to the power $j$, modulo $m$.

Of course these numbers are way too small to provide any security, but that's the general idea.

share|improve this answer
    
How did you get the number 16 from 64? I thought it must be always 64 no metter what. And how did you get the i,j numbers from that exactly? –  Byakugan Jun 12 '13 at 10:25
    
We can use either one, both work. Either $(p-1)(q-1)$ or the least common multiple of $(p-1)$ and $q-1$. And you just pick any $i$ that has an inverse $j$ modulo that number. –  Henno Brandsma Jun 12 '13 at 11:37
    
Ok thank you I uderstand now why I can choose number 16 but still I do not know how to get the keys - which mechanism to use to get them? Or just guessing?? What if I need bigger numbers? –  Byakugan Jun 12 '13 at 14:32
    
Mostly people choose some $i$ that has no divisors in common with $\phi(m)$ (in this case 64), and this is easy to check (Euclid's algorithm) and then $j$ is its inverse (also found by the (extended) Euclidean algorithm). We can choose any such $i$ (and keep its inverse $j$ secret). Often $i=3$ or $i=2^{16}+1$ is chosen, but we need not do that. It's the same for bigger numbers. –  Henno Brandsma Jun 12 '13 at 15:21
    
Question is answered thank you, still do not know how exactly to get the I and J numbers, though. But never mind - for me it would be like step-by-step manual only works :) but thank you anyway. –  Byakugan Jun 13 '13 at 10:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.