Scribd
Upload
131 views

Chap4 RSA Tutorial

RSA encryption uses a public-private key pair to securely transmit messages. Bob generates both keys - a public key to encrypt messages and a private key to decrypt them. Alice uses Bob's public key to encrypt a message and sends it to Bob, who decrypts it with his private key. The security of RSA comes from the difficulty of factoring the product of two large prime numbers.

Uploaded by

Grace Xiao Han
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
131 views

Chap4 RSA Tutorial

RSA encryption uses a public-private key pair to securely transmit messages. Bob generates both keys - a public key to encrypt messages and a private key to decrypt them. Alice uses Bob's public key to encrypt a message and sends it to Bob, who decrypts it with his private key. The security of RSA comes from the difficulty of factoring the product of two large prime numbers.

Uploaded by

Grace Xiao Han
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

RSA Encryption – Tutorial

RSA = (Ron Rivest, Adi Shamir and Les Adleman)

How does Public-Key encryption work?


Let's assume we have two parties, Bob and Alice, who wish to transmit
confidential information to one another over the Internet. Alice would like to send
Bob a corporate document using a Public Key encryption system. To accomplish a
secure transmission, they will need to do the following :-

• Alice and Bob agree on a public-key cryptosystem.


• Bob generates a pair of mathematically linked keys : one public, one private.
• Bob transmits his public key to Alice over any insecure medium.
• Bob keeps the private key a secret.
• Alice uses Bob's public key and the encryption algorithm to encrypt her
message, creating a ciphertext.
• Alice transmits the ciphertext to Bob.
• Bob decrypts the ciphertext using the same algorithm and his private key.

The RSA cryptosystem is based on modular exponentiation modulo the


product of 2 large primes. Each individual has an encrypting key
consisting of a
modulus n = pq,
where p & q are large primes, say with 200 digits each, and an
exponent e
that is relatively prime to (p-1)(q-1).

To produce a usable key, 2 large primes must be found (this can be done
quickly on a computer using probabilistic primality tests). However the
product of these primes n = pq, with approximately 400 digits, cannot be
factored in a reasonable length of time.

RSA Encryption
In the RSA encryption method, messages are translated into sequences of integers.
This can be done by translating each letter into an integer, as is done with the
Caesar cipher. These integers are grouped together to form larger integers, each
representing a block of letters.

The encryption proceeds by transforming the integer M, representing the plaintext


(the original message) to an integer C, representing the ciphertext (the encrypted
message) using the function.
C = Me mod n
Below I'll show you an example of using RSA encryption,

for practical reasons I've used small primes p and q, rather than primes
with 100 or more digits. Obviously this cipher ISN'T secure.

We select 2 primes, p = 43 & q = 59 so that n = 43 · 59 = 2537, and with


e = 13.
gcd (e,(p-1)(q-1) = gcd(13,42*58) = 1
(gcd = greatest common divisor)
Lets take the hypothetical message STOP, first we'll convert the letters
into their numerical equivalents (position in the alphabet-1) and then
group those numbers into blocks of 4.
1819 1415 = ST OP

We encrypt each block using the mapping:


C = M13 mod 2537
Computations using modular multiplication show that
181913 mod 2537 = 2081, and
141513 mod 2537 = 2182.
The encrypted message is thus
2081 2182.

RSA Decryption
The plaintext message can be quickly recovered when the decryption
key d, an inverse of
e modulo (p-1)(q-1)
is known. (Such an inverse exists since gcd(e,(p-1)(q-1))=1).

Using the simple cipher above we receive the message


0981 0461,
lets go about decrypting it.
n = 43 · 59 and
e (exponent) = 13,
we can work out that
d = 937 is an inverse of 13 modulo 42 · 58 = 2436.
We therefore use 937 as our decryption exponent, therefore.
P = C937 mod 2537
Using fast modular exponentiation (an algorithm) we compute
0981937 mod 2537, = 0704 and
0461937 mod 2537 = 1115.
Quick translation reveals that this message was
HELP.

You might also like