Chapter 7

Public Key Cryptography and RSA

Introduction
•Asymmetric encryption is a form of cryptosystem in which
encryption and decryption are performed using the different
keysone a public key and one a private key. It is also known
as public-key encryption.
•Asymmetric encryption transforms plaintext into ciphertext
using a one of two keys and an encryption algorithm. Using the
paired key and a decryption algorithm, the plaintext is recovered
from the ciphertext.
•Asymmetric encryption can be used for confidentiality,
authentication, or both.
•The most widely used public-key cryptosystem is RSA. The
difficulty of attacking RSA is based on the difficulty of finding the
prime factors of a composite number.
Principles of public key cryptosystems
• The concept of public-key cryptography evolved from
an attempt to attack two of the most difficult
problems associated with symmetric encryption
- Key distribution: how to have secure
communications in general without having to trust a
KDC with your key
- Digital signature: how to verify a
message comes intact from the claimed sender
 Private-Key Cryptography
• traditional private/secret/single key
cryptography uses one key
• shared by both sender and receiver
• if this key is disclosed communications are
compromised
• also is symmetric, parties are equal
• hence does not protect sender from receiver
forging a message & claiming is sent by sender
 Public-Key Cryptosystems
• Asymmetric algorithms rely on one key for
encryption and a different but related key for
decryption. These algorithms have the following
important characteristic:
 It is computationally infeasible to
determine the decryption key given only knowledge
of the cryptographic algorithm and the encryption
key.
 Either of the two related keys can be used for
encryption, with the other used for decryption
Ingredients of public key cryptosystem
• Plaintext: This is the readable message or data that
is fed into the algorithm as input
• Encryption algorithm: The encryption algorithm
performs various transformations on the plaintext
• Public and private keys: This is a pair of keys that
have been selected so that if one is used for
encryption, the other is used for decryption
• Ciphertext: This is the scrambled message produced
as output.
• Decryption algorithm: This algorithm accepts
the ciphertext and the matching key and
produces the original plaintext
 Essential steps
1. Each user generates a pair of keys to be used for
the encryption and decryption of messages( private
and public keys)
2. Each user has to place the public key in public
register
3. If Bob wishes to send a confidential message to
Alice, Bob encrypts the message using Alice's public
key.
4. When Alice receives the message, she decrypts it
using her private key.
 Comparisons
Conventional Public key
• The same algorithm with • One algorithm is used for
the same key is used for encryption and decryption
encryption and decryption. with a pair of keys, one for
• The sender and receiver encryption and one for
must share the algorithm decryption.
and the key. • The sender and receiver
must each have one of the
matched pair of keys (not
the same one).
Conventional Publickey
• The key must be kept secret. • One of the two keys must be
• It must be impossible or at least kept secret.
impractical to decipher a • It must be impossible or at least
message if no other information impractical to decipher a
is available. message if no other information
• Knowledge of the algorithm plus is available.
samples of ciphertext must be • Knowledge of the algorithm plus
insufficient to determine the key. one of the keys plus samples of
ciphertext must be insufficient to
determine the other key.
 Why Public-Key Cryptography?
• developed to address two key issues:
– key distribution – how to have secure
communications in general without having to trust
a KDC with your key
– digital signatures – how to verify a message
comes intact from the claimed sender
• public invention due to Whitfield Diffie &
Martin Hellman at Stanford Uni in 1976
– known earlier in classified community
 Public-Key Cryptography
• public-key/two-key/asymmetric cryptography
involves the use of two keys:
– a public-key, which may be known by anybody, and can be
used to encrypt messages, and verify signatures
– a private-key, known only to the recipient, used to
decrypt messages, and sign (create) signatures
• is asymmetric because
– those who encrypt messages or verify signatures cannot
decrypt messages or create signatures
Public-Key Cryptography
 Public-Key Characteristics
• Public-Key algorithms rely on two keys where:
– it is computationally infeasible to find decryption key
knowing only algorithm & encryption key
– it is computationally easy to en/decrypt messages when
the relevant (en/decrypt) key is known
– either of the two related keys can be used for encryption,
with the other used for decryption (for some algorithms)
 Details of public key
• The source A generate the plain text X
• B generates a related pair of keys: a public
key, PUb, and a private key, PRb. PRb is known
only to B
• Y = E(PUb, X)
• X = D(PRb, Y)
Secrecy
Authentication
Steps
• A prepares a message to B and encrypts it
using A's private key
• B can decrypt the message using A's public
key
Therefore, the entire encrypted message serves
as a digital signature
 Public-Key Applications
• can classify uses into 3 categories:
– encryption/decryption (provide secrecy)
– digital signatures (provide authentication)
– key exchange (of session keys)
• some algorithms are suitable for all uses,
others are specific to one
 Security of Public Key Schemes
• like private key schemes brute force exhaustive
search attack is always theoretically possible
• but keys used are too large (>512bits)
• security relies on a large enough difference in
difficulty between easy (en/decrypt) and hard
(cryptanalyse) problems
• more generally the hard problem is known, but is
made hard enough to be impractical to break
• requires the use of very large numbers
• hence is slow compared to private key schemes
 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
– nb. exponentiation takes O((log n)3) operations (easy)
• uses large integers (eg. 1024 bits)
• security due to cost of factoring large numbers
– nb. factorization takes O(e log n log log n) operations (hard)
 Description of algorithm
• makes use of an expression with exponentials
• Plaintext is encrypted in blocks
• with each block having a binary value less
than some number n
• for some plaintext block M and ciphertext
block C:
C = Me mod n
M = Cd mod n = (Me)d mod n = Med mod n
• Both sender and receiver must know the value
of n
• The sender knows the value of e, and only the
receiver knows the value of d
• thus, this is a public-key encryption algorithm
– public key of PU = {e, n}
– private key of PR = {d, n}
For the algorithm to be satisfactory, the
following criterias should be satisfied
• It is possible to find values of e, d, n such
that Med mod n = M for all M < n.
• It is relatively easy to calculate mod Me mod n
and Cd for all values of M < n.
• It is infeasible to determine d given e and n.
 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
– note ø(n)=(p-1)(q-1)
• selecting at random the encryption key e
• where 1<e<ø(n), gcd(e,ø(n))=1
• solve following equation to find decryption key d
– e.d Ξ 1 mod ø(n) and 0≤d≤n
• publish their public encryption key: PU={e,n}
• keep secret private decryption key: PR={d,n}
 RSA Use
• to encrypt a message M the sender:
– obtains public key of recipient PU={e,n}
– computes: C = Me mod n, where 0≤M<n
• to decrypt the ciphertext C the owner:
– uses their private key PR={d,n}
– computes: M = Cd mod n
• note that the message M must be smaller
than the modulus n (block if needed)
 RSA Example - Key Setup
1. Select primes: p=17 & q=11
2. Compute n = pq =17 x 11=187
3. Compute ø(n)=(p–1)(q-1)=16 x 10=160
4. Select e: gcd(e,160)=1; choose e=7
5. Determine d: de=1 mod 160 and d < 160
Value is d=23 since 23x7=161= 10x16+1
6. Publish public key PU={7,187}
7. Keep secret private key PR={23,187}
 RSA Example - En/Decryption
• sample RSA encryption/decryption is:
• given message M = 88 (nb. 88<187)
• encryption:
C = 887 mod 187 = 11
• decryption:
M = 1123 mod 187 = 88
 RSA Security
• possible approaches to attacking RSA are:
– brute force key search (infeasible given size of
numbers)
– mathematical attacks (based on difficulty of
computing ø(n), by factoring modulus n)
– timing attacks (on running of decryption)
– chosen ciphertext attacks (given properties of
RSA)