Lecture 3 RSA

Public Key Cryptography
The development of public-key cryptography is the greatest and perhaps the only true
revolution in the entire history of cryptography.
Asymmetric Cryptography (also called Public-Key Cryptography) was a real

breakthrough in cryptography. The major change between asymmetric cryptography and
the ‘traditional’ symmetric cryptography is that, in asymmetric cryptography, the key for
the encryption is not the same as the key for the decryption. Each user has 2 keys: a
Public Key, which is known to all, and a Private Key, which is kept secret (private).
Denote Bob’s public key by PU(B), and denote Bob’s private key by PR(B).
Public-key cryptography provides a radical departure from all that has gone before. For
one thing, public-key algorithms are based on mathematical functions rather than on
substitution and permutation. More important, public-key cryptography is asymmetric,
involving the use of two separate keys, in contrast to symmetric encryption, which uses
only one key. The use of two keys has profound consequences in the areas of
confidentiality, key distribution, and authentication
The concept of public-key cryptography evolved from an attempt to attack two of the
most difficult problems associated with symmetric encryption. The first problem is that
of key distribution. Key distribution under symmetric encryption requires either (1) that
two communicants already share a key, which somehow has been distributed to them; or
(2) the use of a key distribution center.
The second is the authentication the way that identifies the sender.
The first use of public key cryptography is for encrypting messages to Bob. Anyone who
wishes to send an encrypted message to Bob will use Bob’s public key. To decrypt the
message, Bob’s private key is needed, and only Bob knows it.
Alice PUb PRb Bob
Message Cipher Message

Encryption Decryption
1
The second use of public key cryptography is for message signing by Bob. Bob’s private
key is used by Bob to generate a signature. Any one is able to verify Bob’s signature
using Bob’s public key. Denote the signature of the message M by (M).
Alice PUb PRb Bob
Message, Message,
Yes/No Message
Verification (M) Authentication
The encryption (or verification) algorithm and the decryption (or authentication)
algorithms may or may not be the same.
However, it is possible to provide both the authentication function and confidentiality

by a double use of the public-key scheme.
2
History of Public Key Cryptography
1976 – Diffie & Hellman published an article ‘Public Key Cryptography’ that presented
the model. They got a patent but never used it to license the technology. They also
came up with a protocol for a Key Exchange protocol based on their method.
1977 – Rivest, Shamir, and Adleman invented the RSA scheme which provides
Encryption, Signature, and Key Exchange. RSA became the most popular method
for public key cryptography.
Since – Many other methods implemented the public key model. For example:
El Gamal – Encryption, Signature, and Key Exchange (developed by El Gamal).
DSS – Digital Signature Standard (developed by NIST).
DH – Key exchange (developed by Diffie and Hellman).
The table below summarizes some of the important aspects of symmetric (Private-Key
Cryptography) and public-key encryption. To discriminate between the two, we refer
to the key used in symmetric encryption as a secret key (Private-Key Cryptography)
and asymmetric (Public-Key Cryptography)
Private-Key Cryptography Public-Key Cryptography
• The same algorithm with the • One algorithm is used for
same key is used for encryption encryption and decryption with a
and decryption pair of keys, one for encryption
and one for decryption.
• Key is shared by both sender • sender and receiver used different
and receiver keys
• Also known as symmetric, both • Asymmetric since parties are not
parties are equal equal
• Provide secrecy • Provide secrecy, authentication
and session keys.
• For example DES cipher • For example RSA cipher algorithm.
algorithm.
3
RSA Algorithm
The algorithm was developed 1977 by Ron Rivest, Adi Shamir, and Len Adleman at
MIT and first published in 1978. The RSA scheme has since that time reigned supreme
as the most widely accepted and implemented general-purpose approach to public-key
encryption.
It is a block cipher in which the plaintext and ciphertext are integers between 0 and n 1
for some n.
The algorithm consists of below:

4 Part #1 : Key Generation
- Select p , q where: p and q both prime, p ≠ q

- Calculate n= p x q
- Calculate φ (n)=( p−1)(q−1)
- Select integer e where: gcd ¿
- Calculate d where: d ≡e−1 (mod φ ( n ))
- Public Key PU ={e , n }
- Private Key RP={d , p , q }
4 Part #2: Encryption:

- Plaintext: M<n
- Ciphertext: C=M mod n
e
4 Part #3 Decryption:
- Ciphertext: C
- Plaintext M =C d mod n
Example:
4
Suppose p=17, q=11. Using RSA to encrypt the message M=88
Solution:
- n=p*q  17*11 =187
- φ (n) = (p-1)(q-1) = 16*10
=160
- choose e verifies gcd ¿
then e=7
- choose d verifies e .d ≡1 mod φ ( n ), then d=23
7.23 ≡1 mod 160
- PU={7, 187}
- PR={23,17,11}
To encrypt m=88 using the encryption formula

C=M e mod n  887 mod 187 =11
The decryption:
d
M =C mod n
23
M =11 mod 187=88
Fast Exponentiation Algorithm:

The formula a b mod n could be calculated faster by converting the value of b to binary
scheme, then do the square and multiplication. If bi=0, then do the square only, else do
square and multiply together. Below the pseudo code explain the algorithm.
5
Example: what is the Result of the Fast Modular Exponentiation Algorithm for ab mod n,
where a = 7, b = 560, n = 561.
Solution:
Note that the variable c is not needed; it is included for explanatory purposes. The final
value of c is the value of the exponent. Note: The integer b is expressed as a binary
number bk bk-1 ... b0. The value of b should convert to binary scheme, so b=
1000110000. Table below shows the result of algorithm application
560
∴7 mod 561=1
6
Assignment:
1. If p=61, q= 53, e=17 and the encrypted message C= 855. What is the original
message m?
2. The ciphertext C =10 sent to a user whose public key is e=5, n=35. What is the
plaintext M?
Applications for Public-Key Cryptosystems

In broad terms, we can classify the use of public-key cryptosystems into three categories:
 Encryption/decryption: The sender encrypts a message with the recipient's
public key.
 Digital signature: The sender "signs" a message with its private key.
Signing is achieved by a cryptographic algorithm applied to the message or
to a small block of data that is a function of the message.
 Key exchange: Two sides cooperate to exchange a session key. Several
different approaches are possible, involving the private key(s) of one or both
parties.
Some algorithms are suitable for all three applications, whereas others can be used only
for one or two of these applications. Following Table indicates the applications
supported by the algorithms discussed in this book.
Table Applications for Public-Key Cryptosystems
Algorithm Encryption/Decryption Digital Signature Key Exchange

RSA Yes Yes Yes
Elliptic Curve Yes Yes Yes
Diffie-Hellman No No Yes

Lecture 3 RSA

Uploaded by

Copyright:

Available Formats

Lecture 3 RSA

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Lecture 3 RSA

Uploaded by

Copyright:

Available Formats

Public Key Cryptography

Asymmetric Cryptography (also called Public-Key Cryptography) was a real

Alice PUb PRb Bob

Message Cipher Message

Alice PUb PRb Bob

However, it is possible to provide both the authentication function and confidentiality

The algorithm consists of below:

- Select p , q where: p and q both prime, p ≠ q

4 Part #2: Encryption:

To encrypt m=88 using the encryption formula

Fast Exponentiation Algorithm:

Applications for Public-Key Cryptosystems

Algorithm Encryption/Decryption Digital Signature Key Exchange

You might also like