Scribd
Upload
4 views15 pages

2 2 PubKey-RSA

RSA is a widely used public key cryptosystem developed by Rivest, Shamir, and Adleman in 1977, which relies on the difficulty of factoring large integers for its security. The key generation process involves selecting two large prime numbers, computing their product and totient, and determining the public and private keys. Encryption and decryption are performed using modular exponentiation with the public and private keys, respectively.

Uploaded by

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

2 2 PubKey-RSA

RSA is a widely used public key cryptosystem developed by Rivest, Shamir, and Adleman in 1977, which relies on the difficulty of factoring large integers for its security. The key generation process involves selecting two large prime numbers, computing their product and totient, and determining the public and private keys. Encryption and decryption are performed using modular exponentiation with the public and private keys, respectively.

Uploaded by

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

Public Key Cryptosystems

RSA
• By Rivest, Shamir & Adleman of MIT in 1977
• Best known & widely used public-key scheme
• based on exponentiation in a finite (Galois) field over
integers modulo a prime
– exponentiation takes O((log n)3) operations (easy)
• uses large integers (eg. 1024 bits)
• security due to cost of factoring large numbers
– factorization takes O(e log n log log n) operations (hard)
RSA Key Setup
Each user generates a public/private key pair by:
• selecting two large primes at random ‘p’, q’
• computing their system modulus n = p.q
(n) = (p-1)(q-1)
• selecting at random the encryption key e
• where 1<e< (n), gcd(e,(n)) =1
• i.e. Select e , such that e is relatively prime to (n)

• solve following equation to find decryption key d


e.d 1 mod (n) and 0 ≤ d ≤ n (d  e-1 mod (n) )

• Publish their Public Encryption Key : KU={e,n}


• Keep Secret Private Decryption Key : KR={d,p,q}
RSA – Key : Example
1. Select primes: p=17 & q=11
2. Compute n = pq =17×11=187
3. Compute (n)=(p–1)(q-1)=16×10=160
4. Select e ; choose e=7 ( gcd(e,160)=1 )
5. Determine d: de  1 mod 160 and d < 160
value is d=23 (since 23×7=161 => 10×16 +1)
6. Publish public key KU={7,187}
7. Keep secret private key KR={23,17,11}
Crypt using RSA
• to encrypt a message M the sender:
– obtains public key of recipient KU={e,n}
– computes: C=Me mod n, where 0≤M<n

• to decrypt the cipher text C the owner:


– uses their private key KR={d,p,q}
– computes: M=Cd mod n

• note that the message M must be smaller than the modulus n


RSA – encryption/decryption : Example

• sample RSA encryption/decryption is:


– Message (Plain Text) M = 88 (88<187)
– Encryption:
C = Me mod n
C = 887 mod 187 = 11
– Decryption:
M=Cd mod n
M = 1123 mod 187 = 88
Algorithm - RSA Key Generation
RSA – Key : Example-2
• Choose p = 3 and q = 11
• Compute n = p * q = 3 * 11 = 33
• Compute φ(n) = (p - 1) * (q - 1) = 2 * 10 = 20
• Choose e such that 1 < e < φ(n) ( e and φ (n) are coprime)
Let e = 7
• Compute a value for d such that (d * e) % φ(n) = 1.
By solving, d = 3 [(3 * 7) % 20 = 1]
• Public key is (e, n) => (7, 33)
• Private key is (d, n) => (3, 33)

The encryption of m = 2 is c = 27 % 33 = 29

The decryption of c = 29 is m = 293 % 33 = 2


In a nutshell – recall RSA entire process…
Contribution of Maths in RSA
RSA Works well :-
• because of Euler's Theorem and Fermat’s Theorem:
– aø(n)mod N = 1
• where gcd(a,N)=1
– N=p.q
– ø(N)=(p-1)(q-1)
– carefully chosen e & d to be inverses mod ø(N)
– hence e.d=1+k.ø(N) for some k

• hence :
Cd = (Me)d = M1+k.ø(N) = M1.(Mø(N))q
= M1.(1)q = M1 = M mod N

You might also like