Scribd
Upload
15 views1 page

RSA Encryption Example Explained

1. Bob generates his public and private RSA keys by choosing prime numbers p=31 and q=23, computing n=pq=713 and r=(p-1)(q-1)=660, selecting a public exponent e=223 relatively prime to r, and calculating the private exponent d=367 using the extended Euclidean algorithm. 2. Alice encrypts the message 439 by computing the ciphertext 284 as c=me mod n. She sends 284 to Bob. 3. Bob decrypts the message by computing the plaintext 439 as m=cd mod n.

Uploaded by

AppleCake
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd
15 views1 page

RSA Encryption Example Explained

1. Bob generates his public and private RSA keys by choosing prime numbers p=31 and q=23, computing n=pq=713 and r=(p-1)(q-1)=660, selecting a public exponent e=223 relatively prime to r, and calculating the private exponent d=367 using the extended Euclidean algorithm. 2. Alice encrypts the message 439 by computing the ciphertext 284 as c=me mod n. She sends 284 to Bob. 3. Bob decrypts the message by computing the plaintext 439 as m=cd mod n.

Uploaded by

AppleCake
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd

RSA An Example

Here is an example of the RSA scheme in action. I have chosen primes that are large
enough to be interesting but small enough that you can do all of the arithmetic with a
pen, paper and calculator.
Key Generation
1.
2.
3.
4.
5.

p = 31 q = 23 (chosen at random)
n = 31*23 = 713
r = 30*22 = 660
e = 223
(chosen at random)
d = 367
(computed using Euclids algorithm as below)

660 = 223 * 2 + 214


223 = 214 * 1 +9
214 = 9 * 23 +7
9=7*1+2
7 = 2 * 3 +1

1 = 7 3(2)
1 = 7 3(9-7) = 4(7) 3(9)
1 = 4(214-9(23))-3(9) = 4(214) 95(9)
1 = 4(214) 95(223 214) = 99(214) 95(223)
1 = 99(660 2(223))-95(223)
1 = 99(660)-293(223)
so the inverse of 223 mod 660 = -293 = 367

6. Bobs private key = 367

Bobs public key = (223, 713)

Encryption
Alice wishes to send Bob the message m = 439.
She computes c=439223 mod 713 = 284 (see fast exponent ion table below)
Alice sends the ciphertext 284 to Bob.
Decryption
Bob receives the ciphertext 284 from Alice.
He computes 284367 mod 713 = 439 (see fast exponentiation table below)
He knows the message is 439
439223 mod 713
y
u
1
439
439
211
652
315
36
118
683
377
98
242
98
98
335
335
284

n
223
111
55
27
13
6
3
1
0

284367 mod 713


y
u
1
284
284
87
466
439
656
211
94
315
94
118
397
377
652
242
652
98
439

n
367
183
91
45
22
11
5
2
1
0

You might also like