Public Key cryptography 曹天杰 Tianjie Cao ticao(cumt. edu. cn College of Computer science and echnology, China University of Mining and Technology Xuzhou, China 中国矿业大学计算机科学与技术学院 2003.5.30
1 曹天杰 Tianjie Cao tjcao@cumt.edu.cn College of Computer Science and Technology, China University of Mining and Technology, Xuzhou, China 中国矿业大学计算机科学与技术学院 2003.5.30 Public Key Cryptography
Public Key Cryptography The Inventors Whitfield Diffie and martin hellman 1976 Ralph merkle 1978 Trap Door Alice Bob C fKn(P) f 1 (C B B Encryption with one-way function Computation of inverse function One-way functions extremely expensive are often based on welll Joe known hard problems f KR (c) 2
2 Public Key Cryptography • The Inventors – Whitfield Diffie and Martin Hellman 1976 – Ralph Merkle 1978 C = fKB (P) Encryption with one-way function P = f-1 KB (C,TB) Joe P = f-1 KB (C) Alice Bob KB Computation of inverse function extremely expensive Trap Door One-way functions are often based on wellknown hard problems
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. only three algorithms work well for both encryption and digital signatures: rSA, ElGamal, and Rabin. All of these algorith ms are slow
3 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. Only three algorithms work well for both encryption and digital signatures: RSA, ElGamal, and Rabin. All of these algorithms are slow
Security of Public-Key Algorithms Since a cryptanalyst has access to the public key, he can always choose any message to encrypt Eve can generate a database of all possible session keys encrypted with Bob's public key most public-key algorithms are particularl susceptible to a chosen-ciphertext attack In systems where the digital signature operation is the inverse of the encryption operation this attack is impossible to prevent unless different keys are used for encryption and signatures
4 Security of Public-Key Algorithms • Since a cryptanalyst has access to the public key, he can always choose any message to encrypt. • Eve can generate a database of all possible session keys encrypted with Bob’s public key. • most public-key algorithms are particularly susceptible to a chosen-ciphertext attack • In systems where the digital signature operation is the inverse of the encryption operation, this attack is impossible to prevent unless different keys are used for encryption and signatures
The Knapsack Scheme (Merkle and Hellman, 1978) Given X=(x1,x,,,Xn)and an integer s Finding b=(b, b, .,bn)where b;=0 or 1 such that s==∑b1x NP-Complete in general
5 The Knapsack Scheme (Merkle and Hellman, 1978) • Given X = (x1 , x2 ,…, xn ) and an integer s • Finding B = (b1 , b2 ,…, bn ) where bi = 0 or 1 such that s = = bi xi • NP-Complete in general
Super-Increasing Sequence X=(XI, x2,,n)is super-increasing if ∑ (2, 3, 6, 13, 27, 52)is super-increasing
6 Super-Increasing Sequence • X = (x1 , x2 ,…, xn ) is super-increasing if − = 1 1 i j i j x x • (2,3,6,13,27,52 ) is super-increasing
Greedy method Solve X=(2,36,13,27,52)ands=70 s>52? Yes zb1.s1=70-52=18 18>27?No=>b;=0 ·18>13?Yes=>bA=1.s2=18-13=5 5>6?No=>b2=0 5>3?Yes=>b2=1,S2=5-3=2 B=(12120,1,0,1)
7 Greedy Method • Solve X = (2,3,6,13,27,52 ) and s = 70 • s > 52? Yes ==> b6 = 1, s1 = 70 - 52 = 18 • 18 > 27? No ==> b5 = 0 • 18 > 13? Yes ==> b4 = 1, s2 = 18 - 13 = 5 • 5 > 6? No ==> b3 = 0 • 5> 3? Yes ==> b2 = 1, s2 = 5 - 3 = 2 • b1= 1 • B = (1,1,0,1,0,1)
Greedy method To solve for i=l down to 1 Ifs≥x s=s-X.b.=1 ·Els
8 Greedy Method • To solve: – for i =1 down to 1 • If sxi – s = s-xi , bi = 1 • Else – bi = 0
Knapsack Based Public-Key Key generation Choose a super-increasing sequence ⅹ=( Choose randomly two numbers y and such that GCD(N,Y)=l, and Y>>x
9 Knapsack Based Public-Key • Key Generation: – Choose a super-increasing sequence X = (x1 , x2 ,…, xn ) – Choose randomly two numbers Y and such that GCD(N,Y) = 1, and = n j j Y x 1
Knapsack Based Public-Key Public Key: K=(kI, k,.,kn)where k; =X, n modY Private Keys XN.Y
10 Knapsack Based Public-Key • Public Key: – K = (k1 , k2 ,…, kn ) where ki = xi N mod Y • Private Key: – X, N, Y