Scribd
Upload
166 views2 pages

RSA (Rivest-Shamir-Adleman)

RSA is a public-key cryptographic system proposed by Rivest, Shamir, and Adleman in 1977, utilizing number theory and modular arithmetic for secure encryption and decryption. Users generate a public/private key pair through the selection of large prime numbers and calculations involving modular arithmetic. The document provides examples of key setup and the encryption/decryption process, illustrating how messages can be securely transmitted using RSA.

Uploaded by

ariyanashiq90
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
166 views2 pages

RSA (Rivest-Shamir-Adleman)

RSA is a public-key cryptographic system proposed by Rivest, Shamir, and Adleman in 1977, utilizing number theory and modular arithmetic for secure encryption and decryption. Users generate a public/private key pair through the selection of large prime numbers and calculations involving modular arithmetic. The document provides examples of key setup and the encryption/decryption process, illustrating how messages can be securely transmitted using RSA.

Uploaded by

ariyanashiq90
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

RSA (Rivest–Shamir–Adleman)

RSA was proposed by Rivest, Shamir & Adleman of MIT in 1977. It is a widely used public-key
scheme. The algorithm uses number theory and modular arithmetic along with large integers.
It is a very secure approach due to cost of factoring large numbers.
RSA Encryption/ Decryption
− For encrypting a message M the sender:
o obtains public key of recipient PU = {e, n}
o computes: C = Me mod n, where 0≤M<n
− To decrypt the ciphertext C the owner:
o uses their private key PR = {d, n}
o computes: M = Cd mod n
− It should be noted that the message M must be smaller than the modulus n
RSA Key Set up
Each user generates a public/private key pair by
− selecting two large primes at random: p, q
− computing their system modulus n = p × q
o note, ø(n)=(p-1) × (q-1) reference
− selecting at random the encryption key e
o where 1<e<ø(n), gcd(e, ø(n))=1
− solving the following equation to find decryption key d
o e × d=1 mod ø(n) and 0≤d≤n
o By Euler’s theorem, e × d = 1 + k × ø(n) for some k
The public encryption key is PU= {e, n} which is published and the private decryption key is PR=
{d, n} which is kept secret.
RSA Example
− Key Setup
▪ At first, p and q are selected; p=17 & q=11
▪ Then, n is calculated. n = p × q =17 × 11=187
▪ ø(n) is calculate. ø(n)=(p–1) × (q-1) = 16 × 10=160
▪ e is selected so that gcd(e,160) = 1; e=7
▪ d is determined. d × e = 1 mod 160 & 0≤d≤187. d=23 as, 23×7= 161= 1×160+1
▪ Public key PU= {7, 187} is published.
▪ Private key PR= {23, 187} is kept secret.
− Encryption/Decryption
Sample RSA encryption/decryption is:
❖ Given message M = 88 (nb. 88<187)
❖ Encryption: C = 887 mod 187 = 11
▪ Exploiting the properties of modular arithmetic, following can be done:
887 mod 187 = [(884 mod 187) × (882 mod 187) × (881 mod 187)] mod 187
❖ Decryption: M = 1123 mod 187 = 88
RSA Example with text

p = 73, q = 151
n = 11023
ø(n) = 10800
e = 11
d = 5891
Text = How are you?
H= 33 a= 00 y= 24
o= 14 r= 17 o= 14
w= 22 e= 04 u= 20
_ 62 _ 62 ?= 66
M1 = 3314 M2 = 2262 M3 = 0017
M4 = 0462 M5 = 2414 M6 = 2066
C1 = 331411 mod 11023 = 10260
C2 = 226211 mod 11023 = 9489
C3 = 1711 mod 11023 = 1782
C4 = 46211 mod 11023 = 727
C5 = 241411 mod 11023 = 10032
C6 = 200611 mod 11023 = 2253
M1 = 102605891 mod 11023 = 3314
M2 = 94895891 mod 11023 = 2262
M3 = 17825891 mod 11023 = 0017
M4 = 7275891 mod 11023 = 0462
M5 = 100325891 mod 11023 = 2414
M6 = 22535891 mod 11023 = 2006

You might also like