Following on from some stuff I was doing about TLS, I remembered some concept examples of security.
How do I securely send you a present when bad guys are intercepting our mail?
I want to send you a present, but I do not have a padlock from you to lock the box. If you send me a padlock – that would solve the problem – except for the bad guys intercepting the mail and replacing your padlock with theirs. I put something in the box, and lock it using the padlock I received. The bad guys open the box with their key, take out the gold bar, and put in a one pence coin – and then put your padlock on it. You open the box and are disappointed.
One way of doing it is as follows
- I put the present in the box and put my padlock on it, and send it to you
- You receive the box, put your padlock on it – and send the box back to me
- I take my padlock off – and send the box to you again
- You open the box and love the present.
The bad guys cannot get into the box (well, in real life they could).
How do we lock/unlock this gate
The traditional way is to put a chain around the gate, and put a padlock on it. You give a copy of the key to all those who need access. Every one having the same key is not a good idea. You could copy the key 100 times and give it to all your friends, and we quickly lose control of the access.
Another way is for each person to provide their own padlock. We chain the padlocks together, so we have chain, chain, my padlock, your padlock, someone else’s padlock – chain – chain.
This way we are all able to open our padlock and individually we can manage the keys (so you can make 100 copies).
How do I encrypt for multiple recipients?
If I have a 1GB record I want to send to you, I can encrypt it with your public key and send it to you. You need your private key to decrypt it. This is well known.
I want to send the 1GB record to 100 people. I could encrypt it 100 times, once per public key. This would be 100GB. The costs of this soon mounts up.
One solution is to encrypt it with a key. You then encrypt the decryption key with each person’s public key, and stick them on the front of the data. So you have 100 short blocks, followed by a 1GB encrypted block of data.
When you receive it, you iterate over the short blocks until you find one where your private key matches. You decrypt it, then used the decrypted value to decrypt the main 1GB data.
Warning brain ache ahead: Homomorpic encryption
You have been asked to create a voting system. People press one of two buttons, and your code increments the counter for each button. The requirement is that the totals for each button cannot be displayed until the voting period has finished.
Easy you think.
Store the count in an field. When you need to increment the value, decrypt it, add one, and re-encrypt it. Easy; except for the tiny weeny problem that someone with a debugger can step through the code and display the unencrypted value.
Enter Homomorphic encryption. You can do calculations on encrypted numbers.
- You generate a special private/public key pair priv, pub = generate_keypair(128)
- You lock the private key in a safe – with a time lock on it
- You store the public value in your voting machine
- You code has
- button1 = encrypt(pub, 0)
- button2 = encrypt(pub, 0)
- Loop…
- if button1 is pressed then button1 = button1 + encrypt(pub,1)
- if button2 is pressed then button2 = button2 + encrypt(pub,1)
- After voting has finished you do
- print(decrypt(priv, pub, button1))
- print(decrypt(priv, pub, button2))
Multiplication based on RSA encryption technique.
To encrypt data using RSA. You have calculate (x**public_key) Modulo N. Where N is a very large number. You can only decrypt it with the private key
- (x **A) * (y **A) = (x*y) **A
Using RSA techniques
- [(x **PublicKey) * (y **PublicKey)] Modulo N = [(x*y) **PublicKey ] Modulo N
To decrypt this you need the private key.
This is the “easy” case for multiplication. There are more complex schemes using Group theory and very large lattices, for addition and subtraction.
It is much more complex than I’ve explained.
ColinPaice 