Public-key cryptography (chapter 5)

Tăng nhanh nhu cầu truyền tải linh hoạt và an toànthông tin cần thiết để sử dụng các phương pháp mật mã mới.Nhược điểm chính của các mật mã học cổ điển là nhu cầuđể gửi một khóa (long) thông qua một kênh an toàn siêu trướcgửi tin nhắn tự.IV054Trong mật mã học (symetric key) bí mật-key cả người gửi và ngườinhận chia sẻ cùng một bí mật quan trọng.Trong ryptography khoá công khai có hai khóa khác nhau:một khoá mật mã công cộngvàmột chìa khóa giải mã bí mật (ở phía bên nhận)....
Nội dung trích xuất từ tài liệu:
Public-key cryptography (chapter 5)IV054 CHAPTER 5: Public-key cryptography CHAPTER cryptography Rapidly increasing needs for flexible and secure transmission of information require to use new cryptographic methods. The main disadvantage of the classical cryptography is the need to send a (long) key through a super secure channel before sending the message itself. In secret-key (symetric key) cryptography both sender and receiver share the same secret key. In public-key ryptography there are two different keys: a public encryption key and a secret decryption key (at the receiver side). Public-key cryptography 1IV054 Basic idea - example Basic idea: If it is infeasible from the knowledge of an encryption algorithm ek to construct the corresponding description algorithm dk, then ek can be made public. Toy example: (Telephone directory encryption) U Start: Each user U makes public a unique telephone directory td to encrypt U messages for U and U is the only user to have an inverse telephone directory itd . Encryption: Each letter X of a plaintext w is replaced, using the telephone directory tdU of the intended receiver U, by the telephone number of a person whose name Analogy: letter X. starts with Secret-key cryptography 1. Put the message into a box, lock it with a padlock and Decryption: easy for Uk, with an inverse telephone directory, infeasible for others. send the box. 2. Send the key by a secure channel. Public-key cryptography Open padlocks, for each user different one, are freely available. Only legitimate user has key from his padlocks. Transmission: Put the message into the box of the intended receiver, close the padlock and send the box. Public-key cryptography 2IV054 Public Establishment of Secret Keys Main problem of the secret-key cryptography: a need to make a secure distribution (establishment) of secret keys ahead of transmissions. Diffie+Hellman solved this problem in 1976 by designing a protocol for secure key establishment (distribution) over public channels. Protocol: If two parties, Alice and Bob, want to create a common secret key, then they first agree, somehow, on a large prime p and a primitive root q (mod p) and then they perform, through a public channel, the following activities. • Alice chooses, randomly, a large 1 Ł x < p -1 and computes x • Bob also chooses, again randomly, a large 1 Ł y < p -1 and computes X = q y mod p. • Alice and Bob exchange X and Y, through a public channel, but keep x, y secret. Y = q mod p. x y • Alice computes Y mod p and Bob computes X mod p and then each of them An eavesdropper seems to need, in order to determine x from X, q, p and y from Y, xy q, p, to have a capability to compute discrete logarithms, or to compute q xy from q xas the key h and q y, what is believed to be infeasible. od p. K=q m Public-key cryptography 3IV054 MAN-IN-THE-MIDDLE ATTACK The following attack by a man-in-the-middle is possible against the Diffie-Hellman key establishment protocol. 1. Eve chooses an exponent z. x y 2. Eve intercepts q and q . A xz B yz 4. Eve computes K = q (mod p) and K = q (mod p) . A Alice, not realizing that Eve is in the middle, also computes K and B 6. ob, not realizing that Eve is with Kmiddle, also computes K . At this point he has B Bob decrypts the message in the B and obtains the message. no reason to think that communication was insecure. 7. Meanwhile, Eve enjoys reading Alices message. Public-key cryptography 4 zIV054 Bloms key pre-distribution protocol allows to a trusted authority (Trent) to distributed secret keys to n (n - 1) / 2 pairs of n users. Let a large prime p > n be publically known. The protocol has the following steps: 1. Each user U in the network is assigned, by Trent, a unique public number rU < p. 2. Trent chooses three random numbers a, b and c, smaller than p. 3. For each user U, Trent calculates two numbers U U U U a = (a + br ) mod p, b = (b + cr ) mod p 4. Each user U cvia his the polynomial to U. and sends them reates secure channel gU (x) = aU + bU (x). 5. If Alice (A) wants to send a message to Bob (B), then Alice computes her key KAB = gA (rB) and Bob computes his key KBA = gB (rA). 6. It is easy to see that KAB = KBA and therefore Alice and Bob can now use their (identical) keys to communicate using some secret-key cryptosystem. Public-key cryptography 5IV054 Secure communication with secret-key cryptosystems ...