[go: up one dir, main page]
Scribd
Upload
62 views3 pages

The RSA Algorithm

The RSA Algorithm is a public-key cryptographic method based on the difficulty of prime factorization. It involves generating a key pair from two large prime numbers, with the public key consisting of a modulus and an exponent, while the private key is used for decryption. An example illustrates the encryption and decryption process using specific prime numbers and their corresponding keys.

Uploaded by

Nandini Lokanath
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
62 views3 pages

The RSA Algorithm

The RSA Algorithm is a public-key cryptographic method based on the difficulty of prime factorization. It involves generating a key pair from two large prime numbers, with the public key consisting of a modulus and an exponent, while the private key is used for decryption. An example illustrates the encryption and decryption process using specific prime numbers and their corresponding keys.

Uploaded by

Nandini Lokanath
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
You are on page 1/ 3

The RSA Algorithm

The Rivest-Shamir-Adleman(RSA) Algorithm is a public-key crypto algorithm. It is based on the


principle that prime factorization of a large composite number is tough. Only the private key of the
receiver can decrypt the cipher message. RSA is a key pair generator.

1. Choose two different large random prime numbers p and q


2. Calculate n = p q
n is the modulus for the public key and the private keys
3. Calculate ϕ ( n ) = ( p − 1 ) ( q − 1 )
4. Choose an integer e such that 1 < e < ϕ ( n ) and e is co-prime to ϕ ( n ) : e and ϕ ( n
) share no factors other than 1; gcd (e, ϕ ( n ))= 1.
5. e is released as the public key exponent
6. Compute d to satisfy the d e ≡ 1 ( mod ϕ ( n ) ) i.e.: d e = 1 + k ϕ ( n ) for some integer k
7. d is kept as the private key exponent

The public key consists of n and e.

RSA Algorithm working example

Alice sends a message as m=44 to Bob

1. Choose two prime numbers: 79, 89.


2. Now n = 79*89 = 7031
3. Compute totient = (p-1)(q-1) = 6864 = t.
4. Find ‘e’ which is coprime with 6864 i.e., gcd(5,6864) = 1, e = 5.
5. Choose d, such that it satisfies de mod Φ(n) = 1 here, d = 1373.

The public key is {5,7031} and The private key is {1373, 7031}

ENCRYPTION: c = m5 mod 7031 = 4119

DECRYPTION: m = c1373 mod 7031.


Fast modular exponentiation- square and multiply algorithm

INPUT 1
INPUT 2 : your NAME
a b c d e f g h i j k l m n o p q r s t u v w x y z
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
+ - * ! @ # $ % ^ & _ / , . ? “ ; : < > ` ~ \ ( ) {
52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77

Example: nandini -> 13 00 13 03 08 13 08


P1 = 130013
P2 = 030813
P3= 082525

NOTE: 1. Use Euclids algorithm to find GCD of numbers- used in selected ‘e’
2. use Fast modular exponentiation method for computing exponents in encryption and
decryption process

You might also like