Oblivious transfer allows a sender to not know the information that a receiver has read. If c is a '0', we will be able to read Message 0, if it is a '1' we will be able to read Message 1:
Oblivious transfer |
Method
So, we are Bob the Investigator and investigating a serious crime, and we suspect that Eve is the person who is involved in the crime. We now need to approach her employer (Alice) and ask for some information on her. So how do we do this without Alice knowing that we suspect Eve? Well oblivious transfer (OT) performs this. Let's say that HackerZForU employ Eve and Trent, and we are only interested in getting information on Eve. Alice runs the company.
Now the method we will use is based on the Diffie-Hellman key exchange (DHE) method, but is modified so that we generated two keys for Alice to pass the data. One will work and the other will be useless. Alice will have no idea which of the keys will work, and the information that we can look at. In this case we'll ask for data from both Eve and Trent, and Alice will not know which of them is the suspect.
First Alice and Bob generate random numbers (\(a\) and \(b\)) and agree on a prime number (\(N\)). Alice then takes a generator value of \(g\) and raises it to the power of \(a\):
\(A = g^a \pmod N \)
She passes this to Bob. If Bob is interested in the first record he calculates \(g\) to the power \(b\), else if it is the second record, he calculates the value passed from Alice (A), and multiplies this value with \(g\) to the power of \(b\). Bob then sends one of these back:
\( if (c==0): B = g^b \pmod N \)
\( if (c==1): B = A \times g^b \pmod N \)
Alice receives the value from Bob (\(B\)). She then calculates two keys: the hash of \(B\) to the power of \(a\), and the hash of \(\frac{B}{A}\) to the power of \(a\).
\( K_0 = \text{Hash}(B^a \pmod N )\)
\( K_1 = \text{Hash}((B/A)^a \pmod N )\)
In this case, we can determine the inverse of \(A \pmod N\) and then multiple the value with \(B\). She then encrypts the two messages (\(M_0\) and \(M_1\)) with each of the keys, and returns the ciphers to Bob.
\( e_0 = E_{K_0}(M_0)\)
\( e_1 = E_{K_1}(M_1)\)
Bob calculates the decryption key (which will only work for one of the them) as the hash of \(A\) to the power of \(b\):
\( K_{bob} = \text{Hash}(A^b \pmod N )\)
Bob will then try to decrypt the two ciphers with \( K_{bob}\) and only one will work.
Presentation
Code
An outline of the code is here:
# Find our more here: # https://asecuritysite.com/encryption/ot from Crypto.Cipher import AES from Crypto.Util.Padding import pad, unpad from Crypto.Util.number import getPrime import Crypto import hashlib import random import sys import libnum g=3 bits=128 a=random.randint(1, 2**64) b=random.randint(1,2**64) c=1 m0='Bob did it' m1='Alice did it' if (len(sys.argv)>1): c=int(sys.argv[1]) if (len(sys.argv)>2): g=int(sys.argv[2]) if (len(sys.argv)>3): m0=str(sys.argv[3]) if (len(sys.argv)>4): m1=str(sys.argv[4]) if (len(sys.argv)>5): bits=int(sys.argv[5]) n = getPrime(bits, randfunc=Crypto.Random.get_random_bytes) Alice=pow(g,a,n) print ("Message 0",m0) print ("Message 1",m1) m0=pad(m0.encode(),16) m1=pad(m1.encode(),16) print('\nBits in prime: ',bits) print('g: ',g,' n: ',n) print('a (Alice random): ',a) print('b (Bob random): ',b) print('\nAlice value: ',Alice) # === Bob calculates === if (c==0): Bob=pow(g,b,n) else: Bob=(Alice*(pow(g,b,n))) % n invAlice =libnum.invmod(Alice, n) # let's get A^{-1} (mod n) # === Alice calculates === key0_bytes=(pow(Bob,a,n) & 0xffffffffffffffff).to_bytes(16,'big') key1_bytes=(pow(Bob*invAlice,a,n) & 0xffffffffffffffff).to_bytes(16,'big') key0 = hashlib.sha256(key0_bytes).digest() key1 = hashlib.sha256(key1_bytes).digest() cipher1 = AES.new(key0, AES.MODE_ECB) cipher2 = AES.new(key1, AES.MODE_ECB) print('\nAlice calculates these keys') print('Key 0: ',key0.hex()) print('Key 1: ',key1.hex()) en0=cipher1.encrypt(m0) en1=cipher2.encrypt(m1) ## === Bob decrypts print('\nBob calculates this key:') Bob_key_bytes=(pow(Alice,b,n) & 0xffffffffffffffff).to_bytes(16,'big') Bob_key = hashlib.sha256(Bob_key_bytes).digest() print('Bob key: ',Bob_key.hex()) cipher1 = AES.new(Bob_key, AES.MODE_ECB) message_0=cipher1.decrypt(en0) message_1=cipher1.decrypt(en1) print('\nBob decrypts the messages:') try: print('Message 0:',unpad(message_0,16).decode()) except Exception: print ("Message 0: not readable") try: print('Message 1:',unpad(message_1,16).decode()) except Exception: print ("Message 1: not readable")
A sample run:
Message 0 It was Bob! Message 1 It was Alice! Bits in prime: 128 g: 3 n: 237711704973059895252541179946135728359 a (Alice random): 2108948494614650760 b (Bob random): 7718248666089572151 Alice value: 139715191493885985788716061158980136355 Alice calculates these keys Key 0: 883f8d46670caf12f74eb80a94596081c613f0ac4fba271679e0ab542c596f80 Key 1: 6581c58555a476c75cd5eae910c8137f8307f673624ede71383069c34dae7b82 Bob calculates this key: Bob key: 883f8d46670caf12f74eb80a94596081c613f0ac4fba271679e0ab542c596f80 Bob decrypts the messages: Message 0: It was Bob! Message 1: not readable