Public-Key Requirements Conditions that these algorithms must fulfill: -It is computationally easy for a party B to generate a pair(public- key PU private key PR) -It is computationally easy for a sender A,knowing the public key and the message to be encrypted,to generate the corresponding ciphertext -It is computationally easy for the receiver B to decrypt the resulting ciphertext using the private key to recover the original message -It is computationally infeasible for an adversary,knowing the public key,to determine the private key -It is computationally infeasible for an adversary,knowing the public key and a ciphertext,to recover the original message -The two keys can be applied in either order 11
11 Public-Key Requirements Conditions that these algorithms must fulfill: ─ It is computationally easy for a party B to generate a pair (publickey PUb, private key PRb) ─ It is computationally easy for a sender A, knowing the public key and the message to be encrypted, to generate the corresponding ciphertext ─ It is computationally easy for the receiver B to decrypt the resulting ciphertext using the private key to recover the original message ─ It is computationally infeasible for an adversary, knowing the public key, to determine the private key ─ It is computationally infeasible for an adversary, knowing the public key and a ciphertext, to recover the original message ─ The two keys can be applied in either order
Public-Key Requirements Need a trap-door one-way function -A one-way function is one that maps a domain into a range such that every function value has a unique inverse,with the condition that the calculation of the function is easy,whereas the calculation of the inverse is infeasible Y=f(X)easy ●X=fl(Y)infeasible A trap-door one-way function is a family of invertible functions f,such that -Y=fk(X)easy,if k and X are known -x=fk(Y)easy,if k and Y are known -X=fk(Y)infeasible,if Y known but k not known A practical public-key scheme depends on a suitable trap-door one-way function 12
12 Public-Key Requirements Need a trap-door one-way function ─ A one-way function is one that maps a domain into a range such that every function value has a unique inverse, with the condition that the calculation of the function is easy, whereas the calculation of the inverse is infeasible ● Y = f(X) easy ● X = f–1(Y) infeasible A trap-door one-way function is a family of invertible functions fk, such that ─ Y = fk(X) easy, if k and X are known ─ X = fk –1(Y) easy, if k and Y are known ─ X = fk –1(Y) infeasible, if Y known but k not known A practical public-key scheme depends on a suitable trap-door one-way function
Mathematics in Public-key Cryptosystems Most public key algorithms are based on modular arithmetics. Modular addition (a+b)mod n Modular multiplication (axb)mod n Modular exponentiation ab mod n 13
13 Mathematics in Public-key Cryptosystems Most public key algorithms are based on modular arithmetics. Modular addition (a+b) mod n Modular multiplication (a×b) mod n Modular exponentiation ab mod n
Modular Addition Addition Modulo 10 0 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 2 3 4 5 6 7 8 9 3 4 5 6 7 8 9 0 1 2 4 5 6 7 8 9 0 2 3 5 6 7 8 9 1 2 3 4 6 7 8 9 0 2 3 7 8 9 0 1 2 3 4 6 8 8 9 0 1 2 3 4 5 6 7 9 9 0 1 2 3 4 5 6 7 8 a's additive inverse is -a 14
14 Modular Addition + 0 1 2 3 4 5 6 7 8 9 0 0 1 2 3 4 5 6 7 8 9 1 1 2 3 4 5 6 7 8 9 0 2 2 3 4 5 6 7 8 9 0 1 3 3 4 5 6 7 8 9 0 1 2 4 4 5 6 7 8 9 0 1 2 3 5 5 6 7 8 9 0 1 2 3 4 6 6 7 8 9 0 1 2 3 4 5 7 7 8 9 0 1 2 3 4 5 6 8 8 9 0 1 2 3 4 5 6 7 9 9 0 1 2 3 4 5 6 7 8 a’s additive inverse is -a Addition Modulo 10