of 5

# Shamir's No-Key Protocol

A brief explanation of the Shamir's three-pass protocol.
Published on: Mar 4, 2016
Published in: Education      Technology
Source: www.slideshare.net

#### Transcripts - Shamir's No-Key Protocol

• 1. Shamir’s three-pass ProtocolSending a message to a second party securely, without the need to exchange or distribute encryption keys.SHARING SECRETS WITHOUT SHARING KEYS…
• 2. The first three-pass protocol was de- BASIC INFO veloped by Adi Shamir circa 1980 but was never actually published (we’ll explain later on). • Adi Shamir • ~1980 It’s name is easily explained by the fact that the sender (A) and the receiver (B) exchange three encrypted • never published messages – none of which is a decryption key (that’s why we also call it the Shamir’s no-key protocol). • passes = messages • also: “no-key” Since all the en– and decryptions are performed locally, there’s no need for key agreement and/or • super-encryption distribution. There is a catch, though! We do need something special… • commutative func. …and that would be a commutative encryption function1.[1] a funct., which allows us to remove a 1st encryption with some key e even though a 2nd encryption with a key k has been performed.
• 3. The initiator A encrypts his message M by his secret PROTOCOL key ka, then B encrypts the message he received by his secret key kb. SPECS Now since {{M}ka}kb = {{M}kb}ka, the agent A can decrypt it and send {M}kb to B.A, B: comm. parties Then, using kb, B can retrieve M.ka, kb: symmetric keysM: message The Shamir algorithm uses exponentiation modulo a large prime as both:  the en– (E(e,m) = me mod p)I. A to B : {M}ka  and decryption (D(d,m) = md mod p) functionsII. B to A : {{M}ka}kb ( where p is a large prime ) For any exponent e in range 1..p-1, gcd(e, p-1) = 1. TheIII. A to B : {M}kb decryption exponent d is chosen such that de ≡ 1 (mod p-1)1.IV. B : M The Shamir protocol has the desired commutativity property since E(a,E(b,m)) = mab mod p = mba mod p = E(b,E(a,m)). [1] it follows from Fermats Little Theorem that D(d,E(e,m)) = mde mod p = m
• 4. Such a nice concept, why don‘t we use it?! The protocol described above does not provide any authentication!Without it, it is susceptible to a man-in-the-middle attack, if the opponent has the ability tocreate false messages (or to intercept andreplace the genuine transmitted messages): I. A to I(B) : {M}ka II. I(B) to A : {{M}ka}ki III. A to I(B) : {M}ki IV. I : M.
• 5. Thank you for your attention! (questions more than welcome) source: http://en.wikipedia.org/wiki/Three-pass_protocol