PUBLIC KEY ENCRYPTION

Page 1

TRAPDOOR ONEWAY FUNCTION

Anybody should be able to compute as its a public key and has two properties

function should be Easy to compute

function should be Hard to reverse

Hence, the function that has above properties is called one-way function

The receiver (the only one entity) will know the trapdoor and this forms a private key

first oneway function MULTIPLICATION OF PRIMES

product = multiple of two large primes on polynomial way

factorization becomes difficult with product of two large primes

e.g. RSA

second way function MODULAR EXPONENTIATION

modular exponentiation with large modulus

exponentiation is raising a number to a power

Modular Exponentiation is raising the number to a power modulo some other number

formula f(b) = a to the power of b mod n

Invented by Rivest, Shamir and Adleman

GENERATING RSA KEY PAIRs

STEP 1 : Generate the RSA modulus

n = product

p = large prime 1 (min 512 bits long)

q = large prime 2 (min 512 bits long)

therefore,

n= p x q

n produced here is called RSA modulus

GENERATING RSA KEY PAIRs

STEP 2 : Generate 'e'

must be greater than 1

cannot be less than (p-1)(q-1)

no number should divide neatly into e and (p-1)(q-1) other than 1

RSA KEY PAIRs = (n,e)

(n,e) is a public key

Generating the private key using (n.e)

Private key is inverse of e modulo (p-1)(q-1)

if d is the private key, then

ed=mod (p-1)(q-1)

Based on elliptical curve variant

Basis for other important cryptographic primitives like Digital Signature Encryption

SETTING UP ElGAMAL

Choose a large prime (p) - has to be a number modulo, size 1024 to 2048 bits

Choose a special key (g)- has to be a primitive modulo, has to be between 1 and (p-1)

Choose a private key (x)- has to be greater than 1 and less than (p-1), randomly generated

Compute the key (y)

y = g power x modulo p

x

y = g mod p

TRAP-DOOR ONEWAY FUNCTION

RSA

ElGamal