Week09b RSA1 slides - cghj PDF

Preview

Summary

cghj...

Description

Public Key Algorithms - RSA

Established Public Key Algorithm Families Public key (asymmetric key) cryptography schemes are all built from one common principle, the one-way function. One-way function A function f () is a one-way function if: y = f (x) is computationally easy, and x = f −1(y) is computationally infeasible. A function is easy to compute if it can be evaluated in polynomial time, i.e., its running time is a polynomial function of the length of the input parameter.

Established Public Key Algorithm Families 1.

Integer factorisation schemes: are based on the fact that it is difficult to factor large integers Example: RSA

2.

Discrete logarithm schemes: based on the fact that it is difficult to compute discrete logarithms. Examples: Diffie–Hellman key exchange Elgamal encryption Digital Signature Algorithm (DSA)

3.

Elliptic curve schemes

Key Lengths and Security Levels An algorithm is said to have a “security level of n bit” if the best known attack requires 2n steps to succeed with certainty (with probability 1). For symmetric algorithms considered to be secure, security level = key length. For asymmetric algorithms the above relation does not hold.

key length

Shamir Rivest

Adleman RSA

Ron Rivest, Adi Shamir, and Leonard Adleman

RSA and Modular Arithmetic • RSA encryption and decryption is done in the finite integer ring Zn. • Modular computations play a central role. • RSA encrypts plaintexts x, where we consider the bit string representing x to be an element in Zn = {0,1, . . . ,n−1}. • As a consequence the binary value of the plaintext x must be less than n. The same holds for the ciphertext.

A ring is an algebraic system like a field – defined over a set of elements and has two operations (+, ). The difference is that in a ring we do not require every non-zero member of have a multiplicative inverse. , with + and  as modulo 26 addition and multiplication operation respectively, is a finite ring.

What do we need to study? •

How encryption and decryption are done.

•

How keys are generated.

•

Establish the correctness of the algorithms – decryption gives us back the original (plaintext) message, which was encrypted.

•

Computational efficiency of the encryption and decryption processes if the respective keys are known.

•

Computational infeasibility of decryption without the knowledge of the private key.

RSA encryption and decryption RSA Encryption

RSA Decryption

Given the public key = kpub and the plaintext x, the encryption function is:

Given the private key = kpr and the plaintext x, the decryption function is:

௞೛ೠ್

where x, y

௘

Zn.

The value e is sometimes referred to as encryption exponent or public exponent.

௞௣௥

where x, y

ௗ

Zn.

The private key d is sometimes called decryption exponent or private exponent.

RSA – key generation Algorithm outputs: 1.

A public key: kpub = and

2.

A private key: kpr =

Steps: 1.

Choose two large primes p and q.

2.

Compute n = p · q.

3.

Compute Φ(n) = (p−1)(q−1).

4.

Select the public exponent e

{2, . . . ,Φ(n)−1} such that

gcd(e,Φ(n)) = 1. 5.

Compute the private key d such that d · e ≡ 1 mod Φ(n)

314763503829234858279838934117794732049

Proof of Correctness For the scheme to work as intended, for n, e and d chosen according to the RSA key generation protocol, and for all x Zn ,it must be true that: ௞೛ೝ

௞೛ೝ ( ௞೛ೠ್

௘ ௗ

௘ௗ

We will not go through the proof here, but Eq. 1 can be proved easily, using the modular arithmetic we know: ௘ௗ

[Eq. 1]

Equation 1 establishes the correctness of the RSA scheme.

End...