Modern Cryptography

Quantum Cryptography (a background)

In this article I hope to illustrate some of the ideas behind the strange topic of Quantum Cryptography, though I won't be discussing cryptography itself, that comes later - just the necessary physics. First we must consider the nature of light (this can be generalised to any particle once we get all quantum mechanical, but let's stick with light for now).

Classically, light can be thought of as a wave. It's a transverse wave meaning that the 'oscillations' of the thing doing the waving are at right angles to the direction that the wave is travelling in. Another example of transverse waves are waves on the surface of water.

Picture showing waves horizontally and vertically polarised

These oscillations defined a 'plane' in which the waves are oscillating, and this plane can be oriented at any angle. Waves on the surface of water are vertically polarised. Though the plane of polarisation can be any angle, it is convenient to pick two planes which are at 90 degrees to each other. We can express any polarisation by talking about how much of each is present. Hence, we can talk of 'vertical' and 'horizontal' polarization. Here is an applet which demonstrates this.

You can see polaroid filters in action if you have a pair of polaroid glasses (often sold as 'anti-glare'). Find a light shining on a surface such as a desk. You don't want to be 'square on' to the surface, the light should be bouncing at an angle, 45 degrees is a good start. For the most obvious effect, don't use a mirror.

Look at the surface through your polaroid glasses, then rotate them 90 degrees, and keep looking. You should see the glare change in brightness. You will find that polaroid glasses are best at reducing glare from horizontal reflections when held normally. (See: Brewsters' Angle)

If you use your glasses for driving, you may find that you have trouble with the LCD screens on petrol pumps, this is because the LCD screen relies on polarising light!

If you take a polarised filter, this will ensure that all the light which passes through has the same polarisation. Classically, if a particular wave comes in with an amplitude of A, and a plane of polarisation at angle θ to the plane of polarisation, the amount of light which emerges has amplitude Acosθ.

Picture showing the effect of multiple polarising filters

Suppose that we have two polaroid filters. Unpolarised light hits the first and emerges polarised. It emerges with amplitude, A (on average). This light hits the second filter. The two filters have an angle θ between their planes of polarisation - the amount of light which emerges is Acosθ. So, if the filters are aligned, the second filter has no effect. If it is turned 90 degrees, no light emerges (note, if it is turned 180 degrees, it has no effect - the sign of the amplitude doesn't matter, it's not 'negative light'!)

(Note that for real filters, there is a little scattering, so 90 degrees doesn't give total black, and zero degrees does give some reduction in intensity)

Imagine we have two filters, aligned at 90 degrees. No light emerges. This is because the cosine of 90 degrees is zero.

Now, insert a filter at 45 degrees between the two. What happens? More 'stuff' can only make the amount of light getting through smaller, right? The cunning reader will have assumed that I wouldn't ask the question if the answer were obvious. Some light emerges. In this circumstance, two filters allows through less light than three.

This counterintuitive result is easily explained. Imagine the second filter is at an angle of θ compared to the first.  The third is at 90 degrees. In other words, the angle from the second is (90-θ). From the first filter, we have light with amplitude Acosθ. This is then reduced by the third filter by cos(90-θ). The overall light intensity is now Acosθ.cos(90-θ) or Asinθcosθ, this reduces to A(sin2θ)/2. In other words, we get most light out when sin2θ=1, or when 2θ=90°, or when θ=45° 

The newly inserted second filter is changing the polarisation of the light.

Take your time on polarisation, it's important that you understand the above if you're to comprehend subsequent articles. We'll put this aside for a while, though - the next step is to talk about photons.

GeoHashing

Via xkcd I learned of a new idea called 'Geohashing' geohashing

Essentially the idea is that based on some seed data, some complicated sums are done to give a location.

People get to that location for a meetup.

A map tool is available which does the sums for you. You set the date, click your area and it gives you a location.

Due to problems with the seed data (US stock market) and time zones a new rule has been introduced today for people east of 30 degrees west. This is taken care of automatically by the map tool. There are several pieces of code for implementing this - though most have yet to be updated to reflect the 30W rule.

The idea is that the seed data is processed using an algorithm called md5. This algorithm produces a 'hash' of the data. it is difficult to find alternate data which produces the same hash. A small change in the data produces a big change in the hash.

The idea of a hash is a way of producing a 'fingerprint' of a file. I.e. I could send you a file, but how would you know it hadn't been tampered with? Well, I could phone you, you could recognise me and I could read you the hash of that file (which you can then generate and check).

A hash can also be used as a zero knowledge proof. I.e. I wanted to prove to you that I had discovered some fact. I might not want you to know the fact (yet). For example, I might know the first line of the 'Times' editorial for next saturday. I could generate a hash of that line and give it to you - when the paper is published that information can be checked.

In this case, the md5 algorithm is used to give a reasonable pseudo-randomisation of one number into another. It's just a bit of fun.

I've not gone to a geohash event myself - but I like the concept.

SHA-1 Broken

SHA-1 which is key to many cryptographic protocols, e.g. PGP, SSH, and the cryptography behind shopping online has been broken. It isn't currently a major issue as large resources are needed, however, work will need to be done to replace the affected algorithms before improvements in technology and in the algorithms make the attack more feasible.

Additional: Bruce Schneier has just written on this issue.

PGP

Previously I have mentioned RSA and Public Key systems as well as briefly mentioning PGP.

The most well known public key system is probably PGP. PGP was created 'for the masses' by Phil Zimmerman.

Good public key systems are vital in todays world to secure everything from online commerce to credit card transactions. You would not be able to have a secure connection to amazon.co.uk or amazon.com without a public key system!

PGP is available in the US from pgp.com. People outside the US should download PGPi. This is essentially the same software, but was originally exported legally by printing the source code, walking it out and then typing it in again (the law is an ass!)

As well as RSA, PGP uses the IDEA algorithm, which is under patent. This gave rise to GPG (GNU Privacy Guard)

When you install PGP or GnuPG you generate a pair of keys, one public, one private. The public key can be freely published. This is mine.

-----BEGIN PGP PUBLIC KEY BLOCK-----
Version: PGP 8.1 - not licensed for commercial use: www.pgp.com

mQGiBDtnCSYRBADtFS8omFu6f+HUGtpqylhFfCXyHwP7LHy6Nzd7SSRzCXzqUv2x
iKwzf0Rz2Qjx8lBmzOd+yBhV7Z8krHXBbNUgAOrFwdTt4aI5zYtWjGqZ11yHECA9
Z3wce73val5J9kzEW/azrLwx+ceZq9IXDBlaqGr1pvqWK7VSLWYOn/znDQCg/1Ee
d1ZxLtePd8ja8RIF21R+JWcD/3MLjGugvnMECDhWlToBq8XV5KhFLCUNHfwqwBUj
jXH6Yj9ZPVwM8lpKqCzMm+EKCr1PoYaz2GaYxnnTpS9ZIzSOf8MBnAfvk5h0la4p
O/0K31J9AiQigs6M/uz3dXtsdTPgKh5zBPSIxWck3o2wutLN/Q/waOO02fn+w/dz
++LNA/9ADBhkiUwVswGcQtsdqknknsDfwYxe64iOivdHVOXjY3vJLb8yt5bTM+NQ
z4x2Ics7w6gXJSOjbNWwir1xTLjOS6DpurIwKfbdvJkGSba3ra9j8L/8Js24X3HI
i7ZodqDHJ5xO2FoHZyEjbM9WS+QrHEnxSBzpVBCYEGoK2bzxmIkAYQQfEQIAIQUC
PSbk6gIHABcMgBHwuBXLpFv6QBc1Igd6eeDO56feBwAKCRBo3MJdJvHk6MaaAKC6
4UyDdx/5kb/neFpclrsaooBVcQCfSp3/d0VXewVufAA9IdcicIQtTICJAGEEHxEC
ACEFAj0m5QYCBwAXDIAR8LgVy6Rb+kAXNSIHenngzuen3gcACgkQaNzCXSbx5Ogp
ewCgp8lQQZVGpokVBWmoRc4dzLe/CaIAn07FKd2laYyE/4Xr54PLrC+c4s4+tCBN
YXJrIEJ1cmJpZGdlIDxtdXJreUBsc3BhY2Uub3JnPokAWAQQEQIAGAUCO2cJJggL
AwkIBwIBCgIZAQUbAwAAAAAKCRBo3MJdJvHk6HYgAJ9i5/Mu6aYB6/6RD3B0MY1L
/jLP+wCffaFjIvUpYlTALcXySMKEVu2BfbGJAEoEEBECAAoFAj0mzQ0DBQF4AAoJ
EHp54M7np94Hv6AAn0NvXsU1lwM8rBjyw6sLnU0nwornAJsGC6ehApDkgSu5HZm0
3YZV6zsE9YkASgQQEQIACgUCPniZZAMFAXgACgkQ+00ldnMyEDRcbQCg6hAbxGIX
6pgz7oysgBnwSaz1kpgAnRS9yzbfRXf+gpJCoWCh6E50MTqg0cp6/wAACzUBEAAB
AQAAAAAAAAAAAAAAAP/Y/+AAEEpGSUYAAQEAAAEAAQAA/9sAQwAKBwcIBwYKCAgI
CwoKCw4YEA4NDQ4dFRYRGCMfJSQiHyIhJis3LyYpNCkhIjBBMTQ5Oz4+PiUuRElD
PEg3PT47/9sAQwEKCwsODQ4cEBAcOygiKDs7Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7
Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7/8AAEQgAkAB4AwEiAAIRAQMRAf/E
AB8AAAEFAQEBAQEBAAAAAAAAAAABAgMEBQYHCAkKC//EALUQAAIBAwMCBAMFBQQE
AAABfQECAwAEEQUSITFBBhNRYQcicRQygZGhCCNCscEVUtHwJDNicoIJChYXGBka
JSYnKCkqNDU2Nzg5OkNERUZHSElKU1RVVldYWVpjZGVmZ2hpanN0dXZ3eHl6g4SF
hoeIiYqSk5SVlpeYmZqio6Slpqeoqaqys7S1tre4ubrCw8TFxsfIycrS09TV1tfY
2drh4uPk5ebn6Onq8fLz9PX29/j5+v/EAB8BAAMBAQEBAQEBAQEAAAAAAAABAgME
BQYHCAkKC//EALURAAIBAgQEAwQHBQQEAAECdwABAgMRBAUhMQYSQVEHYXETIjKB
CBRCkaGxwQkjM1LwFWJy0QoWJDThJfEXGBkaJicoKSo1Njc4OTpDREVGR0hJSlNU
VVZXWFlaY2RlZmdoaWpzdHV2d3h5eoKDhIWGh4iJipKTlJWWl5iZmqKjpKWmp6ip
qrKztLW2t7i5usLDxMXGx8jJytLT1NXW19jZ2uLj5OXm5+jp6vLz9PX29/j5+v/a
AAwDAQACEQMRAD8A7g+Yp65pfOZe+abubHWkySeldljC48XTegqVbjd2GarEUAYp
WQKTLH2og4xTzchhWfd3VvYW7XF1KsUSdWY8VxWr/FGxtt0en27XDjo7cLRyoakz
0F3Q9KgLA9q8YvfiR4guziOZLcZ/5Zp/jWWfFOuNJvOpz5/3zj8qXNBdRtSfQ97z
7UnUV47pvxF1u0YCeVblR1Dj+orvNE8dabqqhJD5E3dW6GrVnsQ01udGVzTSpp6u
kgBVsg96UiglohK0m3FS4pMU7k2IsUVJiincVi1tOM9qAB6VK4GcDpTScdqzub2G
Y4xSHCqWYgADJJp9ch8RNZ+w6K1nDIVmnHO3+73/ADouCVzifH3ip9X1BrO1kP2O
A44PDn1rjDyadIxLZpuK55S5mbJWCiipI4mY8VI0rjVGfWpkkMRDBmVhVmGzDHmp
7nTQtsWXO6hTsbexk1c3PC3je50+4SC7dpbYnBBOSvuK9bgljuIEmiYMjrlSO9fO
sWVkAr1r4b6s1xYyadKctDyn0rojPmWpxyjY7Mim4qUikIqzOxHiin4opisTcg0Y
OadijFQaDcV5L4/u/P8AEcsJ6IAg/KvXcGvDvHInj8TXYYEHdlTWc3oa09GYAtw7
OVHA6VG1sQelbejWYnt97DknFWrnRSsTOO1cjqWdj0FQ5opnMrAcgEdavQRIhA9a
la1ZXFKISWFNzuOFCzJYR83yitARGWPBHXrVaACPBbFaNqUkI2kZ71nc6bJaHK38
Btb0jHBOa6zwLei11q2xnMp2N9KoeINNMiLOi9OuBU3gu3eXxLZKmflkBPsBzXTS
loebWhaTPZsUhFTOo3cdKZtrpTOJojxRUmw+lFO4rFyS22H5eaiKEHpV7O+gRjri
seY3cEUdtebfE7SC1xDfKnDLtYj1r1howR0rz34j3rK0emCEFXj8wP75xUzkrGlK
m3KyON0xEtdNWRh71QvvEEmSkcQC9ya0xDIdGj2fe28Zrl77TXUkyTEtn8K4425t
T05cyj7qHjUllb5sZNSuW27sECqumaTJc3a4BCA8mt+6st0jRLwAOKcmk7IdLnlF
uRzE90rPgFsCtHSZ4llXEpX696pz6e8UzAjNWrK3AIQpx/KrbVjCMKnNdo7GFY7q
0deDlTVfwdcW+m68stwNqgMM46VJpERjwP4TTNQhhtbsQKQDMDnPbPSlGfLqaOiq
jsz1dSHUMuCCM5oOag0hzPpNpJ/eiXP1xzVsxnd0rtTPIlFptEapnk0VOI2JxjFF
Fw5S5GoxyKlAFDKAtMzWRqPI9K86+Jtq0b218BlAjRn69f8AGvQ81keJtHGt6PJb
DAcfMhPrWdRXjob4eahUTZ5jp8q3GnxOQBkc1Q1K1iD5ccDtV+C2OnxtAQVMZIIP
Y1j6tM5bHrXItWeqkXNNaEo0a7V29T6VXmkL3ZG7vjr2qGLS3fTW/ftE788GspxM
kjQlmbjBbPJqopCcrFzVN0UqlxwejCi02swPFVVhJiCMXKr0DHOKfahop1HUE8Vb
JTOtsQV21W8QQPcXkBjjOUGWfsBmrdkpxGDW3pmiy6jqKyMhFumN7Ho3tU6vYSmo
u7Os8PW7Q6HaIww2zdg+/P8AWtUAY5FQrlQAOgp4Y+lda0VjyZPmbZKAKKZuPpRT
ESGZSKj381XDEUpb3pCLAcZ5NKZVqruNIWoAwvE+iW09tLewx7ZwMnHQ15vqEGds
gHKmvY3CyRsjchhg15nqVn5V3NCeisQK5K0eV3R34eo2uVnNwvqTRkBUVQfvNWXd
fafNbdKufUV1KoxVogMVh6jpk0b7tyjPbNTGWp13XKUbeG6lBKSlRjqas2ELrMqS
tuIOc0+2R0XBPFW4E2ybiPpVtszdtzorAZIz2r0bRIwNKhx3Ga81tXCRqM8sa9G0
GXfpUI/ujFXS3OWvsanSlBApmCads4rc5B/FFNAHrRTAh+UUxsZ46VHu55pC/NIQ
9setM5zTS1JuPagCXiuB8VxmLVZGXjdg12N7f2+n2r3NzKI44xlia4rVtQGs7btI
WjRhhQx5I9ayrL3LnRh/jsc/JqEcH3jg96xL/VPtExO/jtWtfWCzoQ3Xsa5m606S
OQgHNYQ5TqnzJaFu3vcNgtwavx3G5lIPFYkNq/Ga0Yk2DArR2IjzPc6C0m3yAnoK
9F8K3am2aEkZByK8vsWIYccV1dhe+TGCrYI71MZWlcqceaNj0cSAUjy56V5zrPxK
TSrcJD5NxcjgoWOf0qv4e+K0V9etDq0aWqN9x1OQPY12RXNsedJ8rsz0gyY6UVDB
NHcQrLC4dHGVYcgiikBaa2TPBNNNoue9PMqICzsAo7k1yPiL4n6LopaG3b7bcrxs
jPyg+7UKLewOSR1TQxRqWfCqBkknpXEeJPiPomlLJBp7fbbkAgGM/Ip+vf8ACvNf
EnjvWvEjNHPOYbYniCLhfx9fxrm+tWlFeZDbZq6x4l1TW5C15dO6k8IDhR+Fa/h3
xNFHAtlfvtC8JIen0NcnQQKmcedWZVObpu6PSpTHNHvikV1boQcg1iX8DB/l/lXJ
xTzwH9zNJHnrtYirH9rX+MfaWP1ANc3sLbM7Prae6NtI3A5H51II9i7pGCjuSa51
7+8k+9cP+BxUDs8hy7sx9zmrVLuS8V2R0765aWnCP5pHZf8AGsy88SX10DHE3koe
ynn86yQOadtq1TS2RhKtKW4nJOSck96ASKWitLGNzrfCnxA1Hw8yW8mLizz/AKtz
yv0NFcjmim3fcFodbr3jXVdfkeOSYxW//PKM4GPf1rl3k3vtA/SnPIIw2Opptqm9
9x6CqbvZEoekCtwRmrYsoFjywOfrSou35gOKe8vygDtVcqFdlUWkZzyRTJLQD7rZ
qZZOxPHtT+pBxn2o5UF2UWtnAyO1RlSvUVo7TntmmlEQ/ONwpOPYdyhzS4x1qe42
hvkUAVX+tRawxR9KOtJ3pxNACGkoooGJjNFLRU2C5//ZiQBGBBARAgAGBQI7Z9kQ
AAoJEGjcwl0m8eToHasAniT3BEwnMkV7iI11F3jrvSQswJ0OAKCT1CBRwidaQ306
VSOvvQGIUG6+x4kASgQQEQIACgUCPSbNGQMFAXgACgkQenngzuen3ge8pwCfaFIx
oaUQpnmUcIKExg2ve51OTVIAn2sF4QB9iN9uLsA8m4K3d0MCNbCTtB5NYXJrIEJ1
cmJpZGdlIDxtYXJrQG11cmt5Lm9yZz6JAEYEEBECAAYFAjzO1LgACgkQaNzCXSbx
5OgcJgCg9Qubc2SqTESCobOa1w3AkSEShZgAn2cVvFD1ge24KV9gAcmrOxUHZGNB
iQBKBBARAgAKBQI9Js0bAwUBeAAKCRB6eeDO56feB+P9AJ9icYV+j3hI6jK+koe9
kTptFeIGKgCfUdFpui9PprZg2LkidElvlQ8BA5OJAEoEEBECAAoFAj54masDBQF4
AAoJEPtNJXZzMhA0aREAnA09lwI0AZah+dNwaIPJ1uJWOshjAKCSWelAPmPg2/Ah
j7Pi63TGOctTirkCDQQ7ZzhwEAgA9kJXtwh/CBdyorrWqULzBej5UxE5T7bxbrlL
OCDaAadWoxTpj0BV89AHxstDqZSt90xkhkn4DIO9ZekX1KHTUPj1WV/cdlJPPT2N
286Z4VeSWc39uK50T8X8dryDxUcwYc58yWb/Ffm7/ZFexwGq01uejaClcjrUGvC/
RgBYK+X0iP1YTknbzSC0neSRBzZrM2w4DUUdD3yIsxx8Wy2O9vPJI8BD8KVbGI2O
u1WMuF040zT9fBdXQ6MdGGzeMyEstSr/POGxKUAYEY18hKcKctaGxAMZyAcpesqV
DNmWn6vQClCbAkbTCD1mpF1Bn5x8vYlLIhkmuquiXsNV6TILOwACAggAwEYciheA
nxYfVmCoz0W5I2QdyF05W+1HARsKJ6G96zi49wbqIUbcYS565yzliXpmLWYNzvSV
pLhZgSR8OAUfufAAtse3rgWcvGuu/gzZbIJUL56pm13Znii1dczSfanEezauePfD
HkIdYPLzS0b5TeKTNQcVN/eVDbTxJCgXFc9bKhGoORQMqIFsPaxKBNrFVuKzIjrD
GJttBBgG1bCkvchu5uyXNynT34OnYrFJr/I23VOZBNB5l+pGb9740YOy++3K7tXW
96YrQAHPyq46sDj79FdoEEnVe1fMFHhq99Tc46i83IiLjKueSgWCZntLOvWH6xov
xj8bqBjEP4z46okAUgQYEQIAEgUCO2fZMQUJAeKFAAUbDAAAAAAKCRBo3MJdJvHk
6MnzAJ0bFxjvQaYUGEFivgIlSHbB5HICCgCgu4ytuAIA20S0GjGUYrNTnBYDVtS5
Ag0EPUhr8BAIAPZCV7cIfwgXcqK61qlC8wXo+VMROU+28W65Szgg2gGnVqMU6Y9A
VfPQB8bLQ6mUrfdMZIZJ+AyDvWXpF9Sh01D49Vlf3HZSTz09jdvOmeFXklnN/biu
dE/F/Ha8g8VHMGHOfMlm/xX5u/2RXscBqtNbno2gpXI61Brwv0YAWCvl9Ij9WE5J
280gtJ3kkQc2azNsOA1FHQ98iLMcfFstjvbzySPAQ/ClWxiNjrtVjLhdONM0/XwX
V0OjHRhs3jMhLLUq/zzhsSlAGBGNfISnCnLWhsQDGcgHKXrKlQzZlp+r0ApQmwJG
0wg9ZqRdQZ+cfL2JSyIZJrqrol7DVekyCzsAAgIH+gKS2yp48WFC7NDpn0+GfPMd
w1RPkKNm+iRTiHaNvaESOtX0BMU2JvMSit8n4OoQYcN2zw13DEXcsEqWZIr84Vfo
/4n3c23fkyKLjO+LsIGSWwsa3xzZ59m6M5jnaLIozJ6rpSmMwEhbAnKYX9EbYNyS
8QokvKkq9RDpf3kuknaji7jOBKUDropwmunkxnwxs8nnL4QjKOqrzoxAhjN3+Fch
U+dA0iI+N8WVBW1QpFnGnrjeNelT+3GM9xgp9WwXPoqCzBCBLCnISh2kp98wqqbd
Urr3lOAKqRCh/y7pZxjfaDHSIKu3JvshPbU78eUCyKzQ3db13SKZ3xcdejUTUJiJ
AFIEGBECABIFAjtn2T0FCQHihQAFGwwAAAAACgkQaNzCXSbx5OiQwQCggTzzS5Xd
WEvp/4dC/FHyPtjBq0IAoMsUEWCM5sNxLSVsnWRitR/cp5ByuQINBD1Ia/AQCAD2
Qle3CH8IF3KiutapQvMF6PlTETlPtvFuuUs4INoBp1ajFOmPQFXz0AfGy0OplK33
TGSGSfgMg71l6RfUodNQ+PVZX9x2Uk89PY3bzpnhV5JZzf24rnRPxfx2vIPFRzBh
znzJZv8V+bv9kV7HAarTW56NoKVyOtQa8L9GAFgr5fSI/VhOSdvNILSd5JEHNmsz
bDgNRR0PfIizHHxbLY7288kjwEPwpVsYjY67VYy4XTjTNP18F1dDox0YbN4zISy1
Kv884bEpQBgRjXyEpwpy1obEAxnIByl6ypUM2Zafq9AKUJsCRtMIPWakXUGfnHy9
iUsiGSa6q6Jew1XpMgs7AAICB/99qncKCwEthpxFkWc7KbfRFyAC/3HPCN50YPoJ
VvMWbzzhGGdd6YvAZcq/8mxNeF5p7y9BeaXE5d7GnhdeW8AIO6MCrJRJONf9Y6NY
X1t96ZK3teQE9/vQ+OpvBElSyj5C2zzmE4YeeqUuBhoyjVO6CFk9tjJwPo34W37t
vlYxqzbClkJGkhk5Wbuu0k08lQuW9l08pH4Yp4vbcjfNG+VauS/3KHuEmC3LQtci
1WXBscSkeI9XHCRvZ2Z3h+snKg5kuIWJk5gIkwHq5+JmU4+dvtPBeA8+Jdq2xTYC
I/aA+lvC5HW0h/jW+whribx1fwqe+DLi+7Os8WBHMS9F/lQwiQBSBBgRAgASBQI7
Z9lMBQkB4oUABRsMAAAAAAoJEGjcwl0m8eTopj4AoIUDAwY0JsvsKWcYxWCm/r9x
WlckAKDjZGZc8l4vohh3fXx2eNwaCR6ql7kCDQQ/KZ9wEAgA9kJXtwh/CBdyorrW
qULzBej5UxE5T7bxbrlLOCDaAadWoxTpj0BV89AHxstDqZSt90xkhkn4DIO9ZekX
1KHTUPj1WV/cdlJPPT2N286Z4VeSWc39uK50T8X8dryDxUcwYc58yWb/Ffm7/ZFe
xwGq01uejaClcjrUGvC/RgBYK+X0iP1YTknbzSC0neSRBzZrM2w4DUUdD3yIsxx8
Wy2O9vPJI8BD8KVbGI2Ou1WMuF040zT9fBdXQ6MdGGzeMyEstSr/POGxKUAYEY18
hKcKctaGxAMZyAcpesqVDNmWn6vQClCbAkbTCD1mpF1Bn5x8vYlLIhkmuquiXsNV
6TILOwACAgf+L0E1MAQP60eaGOo4DuRe0uE8+EjszRHcQSAmnCMfilafsxuId44U
OUD8j5U10Hpym0jcNpXD/y03c4RCn324c60rqCs3S3r15BzlIe1SZ1CXUVGpMrJy
D2aZwM3WDvc9vXdT3GUDb2xwgBciKHPLgOw4dngs8AHU9NMTApPhN/vNR/aDv0Cr
oe/h5KtSUhJHsjFPxgAskYGnQnmKVfuhetrbAQQdwDzzbskLr6qmZJeqN1+Rus7t
9cGpaRABWPLGQpTN4Qo7A0JNyyf61j+hi0qyykuLhloXbraQf1V7YUiMuhBIrwV8
dgqqHXXIku5P7afEIZgw4XGv6JAe5EHBk4kAUgQYEQIAEgUCO2fZXgUJAePWgAUb
DAAAAAAKCRBo3MJdJvHk6LpMAKDkWIJdfV2fhbWTh50ILzv9DKZ03gCdG27THUsc
1fuXKQ9F/2XV1vmYkgW5Ag0EQQwkcBAIAPZCV7cIfwgXcqK61qlC8wXo+VMROU+2
8W65Szgg2gGnVqMU6Y9AVfPQB8bLQ6mUrfdMZIZJ+AyDvWXpF9Sh01D49Vlf3HZS
Tz09jdvOmeFXklnN/biudE/F/Ha8g8VHMGHOfMlm/xX5u/2RXscBqtNbno2gpXI6
1Brwv0YAWCvl9Ij9WE5J280gtJ3kkQc2azNsOA1FHQ98iLMcfFstjvbzySPAQ/Cl
WxiNjrtVjLhdONM0/XwXV0OjHRhs3jMhLLUq/zzhsSlAGBGNfISnCnLWhsQDGcgH
KXrKlQzZlp+r0ApQmwJG0wg9ZqRdQZ+cfL2JSyIZJrqrol7DVekyCzsAAgIH/2nn
7EFbBtP/NfPcPjOxAsCtfGt4nHNuPNdNcv6UnK/VJkOqC3Fst52HVvNYvmzYYrvJ
pAFhxBqzOYMHIz0YDyRcCzxzuwFgvujuw87DPIhZJAmUTVIVgZEgYjyWne7IAXG4
JVkFWHIsKnQg7aOICyPsVseyZ5bhex9dhnfalX32AYGi1KRwUOPGhOYiwKO3QEju
/twre7X6rd177twrJ6pEmv9y40DVyUGP3+1WzDJFuFzBl+nTHkcELFCdUiBFztX8
Fdgcj5/uWp0xo/XmM18DX3NnH34HZmuMog4ZWRm95lIolUTReAY/19xERv3cqFuz
0tNKzbheS/Hi0OLd7QCJAFIEGBECABIFAjtn2XoFCQHihQAFGwwAAAAACgkQaNzC
XSbx5Og+2wCgs3gwNYpKBpw1fAwrYZu9KPH46+0AoNiJe2SCGo2JzUdPFlHQQbbJ
6wgPuQINBELtV/AQCAD2Qle3CH8IF3KiutapQvMF6PlTETlPtvFuuUs4INoBp1aj
FOmPQFXz0AfGy0OplK33TGSGSfgMg71l6RfUodNQ+PVZX9x2Uk89PY3bzpnhV5JZ
zf24rnRPxfx2vIPFRzBhznzJZv8V+bv9kV7HAarTW56NoKVyOtQa8L9GAFgr5fSI
/VhOSdvNILSd5JEHNmszbDgNRR0PfIizHHxbLY7288kjwEPwpVsYjY67VYy4XTjT
NP18F1dDox0YbN4zISy1Kv884bEpQBgRjXyEpwpy1obEAxnIByl6ypUM2Zafq9AK
UJsCRtMIPWakXUGfnHy9iUsiGSa6q6Jew1XpMgs7AAICB/9aE+4pVRkZs5EK5ma6
pEu8X+/YETL8AElJY3a3uJftR2gH0Jr5ra0hG/2+uv7kgbD6hTWN1ODFJDs4K+gF
byIu9fm1o1fxolhG8PLskLCkKhid4svZAAoBxqubnxqyT9exm3aE1fndRTKGjQrA
0Z4z2kJh42TrXo2s9YXE14Xc/HWUGDS62hjTh5Il5KiKQ5C0wSoXdRXjOUeKj1E4
0bQJQh9uNwMdH68IZ1T7e5pb08Pg+VcdZRl30tY63fIMUsgx5aFNHEQ2G02TeWA9
nTPby9aGshUXdtLhKQIWMp80QFPpDF5Bnu2LjJdEje8itqfZZhSd81QUsSNOahcT
lQuRiQBSBBgRAgASBQI7Z9mPBQkB4oUABRsMAAAAAAoJEGjcwl0m8eTooAgAoJfa
wmYbaY82VEZvl7xodj+WnYUwAJ9W1+uTBszZ9slY1jw8fuoUkf4gArkCDQREzotw
EAgA9kJXtwh/CBdyorrWqULzBej5UxE5T7bxbrlLOCDaAadWoxTpj0BV89AHxstD
qZSt90xkhkn4DIO9ZekX1KHTUPj1WV/cdlJPPT2N286Z4VeSWc39uK50T8X8dryD
xUcwYc58yWb/Ffm7/ZFexwGq01uejaClcjrUGvC/RgBYK+X0iP1YTknbzSC0neSR
BzZrM2w4DUUdD3yIsxx8Wy2O9vPJI8BD8KVbGI2Ou1WMuF040zT9fBdXQ6MdGGze
MyEstSr/POGxKUAYEY18hKcKctaGxAMZyAcpesqVDNmWn6vQClCbAkbTCD1mpF1B
n5x8vYlLIhkmuquiXsNV6TILOwACAggAmD63jYEZ9QNlk/klawIsio73dGKvCLA8
kbJEGbtA09NUrwKqr6OZO07eBWczRA3T/cBdLAsgRsYCKut7rKQe7vvZJQ00CVH3
EKsT9jeu1+PGupsvnuYL9wT4Qw+RGSUqHok8ynLInCeX0yCFzx5qBXegXt1G/PYt
RS0fV6Sbm7At87D73MmKtvosa++c0zmMAaFAxsQZp36ioD+RrZ5YbTymythzguWO
wtMmzEtbLYvwJCnuDjo1ZDB/n69pWOyO0VXUVmtZMmNhDlGSzCxqHL0vpzT2urOD
P4C9V43jL2z+qhWUNJWZtVHEmjTHm7ZJs54Ip0prOsYQbviI9YMwzYkAUgQYEQIA
EgUCO2fZogUJAeKFAAUbDAAAAAAKCRBo3MJdJvHk6BzxAJ0YMxGP7xWbhmk710dO
n2Eor8zO1gCg8KEhjAzjRg84xZcycQ9xytrdRMm5Ag0ERq++8BAIAPZCV7cIfwgX
cqK61qlC8wXo+VMROU+28W65Szgg2gGnVqMU6Y9AVfPQB8bLQ6mUrfdMZIZJ+AyD
vWXpF9Sh01D49Vlf3HZSTz09jdvOmeFXklnN/biudE/F/Ha8g8VHMGHOfMlm/xX5
u/2RXscBqtNbno2gpXI61Brwv0YAWCvl9Ij9WE5J280gtJ3kkQc2azNsOA1FHQ98
iLMcfFstjvbzySPAQ/ClWxiNjrtVjLhdONM0/XwXV0OjHRhs3jMhLLUq/zzhsSlA
GBGNfISnCnLWhsQDGcgHKXrKlQzZlp+r0ApQmwJG0wg9ZqRdQZ+cfL2JSyIZJrqr
ol7DVekyCzsAAgIIALlNXxXlHmy22wZ1izfM5moU6NT2Y2nnm22RWVLqbRebwLGf
li+vpYcxX701WmYPnmvjZbBwvkVJs/ZFtwSyc+EIAurp+jBVPl02QkOky9+hW7gw
h6HUoE1bzjof1tW0rGPgssE0sIy1YL5a06okuWOY8k3s8P+XUKh37PE3zF1oiK+d
M5R9iESww10Sk1a0/ionVGfpTHSvaRP4/OPiBtkBm9AzA2jHkNvGA2VawzP2WaAH
ukQ7yo7rm0+GiQaN6zwfm4nEjyimbZNJuBA4Fagcwu00fwU0PIYJMI9j1Ve+ekcG
Z/s5l9rbwfXptVi9Xe+W2fhk0WYyYJjsxXFzbZeJAFIEGBECABIFAjtn2bgFCQHj
1oAFGwwAAAAACgkQaNzCXSbx5OjZqQCeN9YxKRQz95FTww/9u+uSjvE8LaEAoMjN
SY+xOpClmcxsWksip0hu5G2SuQINBEiSQ/AQCAD2Qle3CH8IF3KiutapQvMF6PlT
ETlPtvFuuUs4INoBp1ajFOmPQFXz0AfGy0OplK33TGSGSfgMg71l6RfUodNQ+PVZ
X9x2Uk89PY3bzpnhV5JZzf24rnRPxfx2vIPFRzBhznzJZv8V+bv9kV7HAarTW56N
oKVyOtQa8L9GAFgr5fSI/VhOSdvNILSd5JEHNmszbDgNRR0PfIizHHxbLY7288kj
wEPwpVsYjY67VYy4XTjTNP18F1dDox0YbN4zISy1Kv884bEpQBgRjXyEpwpy1obE
AxnIByl6ypUM2Zafq9AKUJsCRtMIPWakXUGfnHy9iUsiGSa6q6Jew1XpMgs7AAIC
CADRJBr+uUD5BjIKIpdobB3Ydnlcdi83S9eEL/IuBIAJYGoaitV61mat9KmVQ3zA
Xd4mk/7z62hMpY+rB3KKzEIazdhNyZehV0tkqcTpvTH6HlKsAzsNGdLXepsXIq7d
pgyxS4S5RFsYD2KNuO6xQkqDP4E1pnXgtaC54x549niSOrh8Z/FneP6QTIzqDtzS
+HYAzXoH4uevhcUGPhmMqriYxYGkoHdZ5gZbC4b9BwbEyupFe/+PmbUqrt676IrK
fV2YSa70tiCE55tRegcH6k07fj+p1KhAbjb6jiHxsUeHEAVcxHlXKBAcIH+wEe5r
6T3BeMizVqxa9TVN2Yfy3mM6iQBSBBgRAgASBQI7Z9nLBQkB4oUABRsMAAAAAAoJ
EGjcwl0m8eToP44An2hCI4uKUIXUs3FYotw5uS26cPEEAJ46DDFv0MNzs+2wotHa
1GAI3eOqGbkCDQRKc3dwEAgA9kJXtwh/CBdyorrWqULzBej5UxE5T7bxbrlLOCDa
AadWoxTpj0BV89AHxstDqZSt90xkhkn4DIO9ZekX1KHTUPj1WV/cdlJPPT2N286Z
4VeSWc39uK50T8X8dryDxUcwYc58yWb/Ffm7/ZFexwGq01uejaClcjrUGvC/RgBY
K+X0iP1YTknbzSC0neSRBzZrM2w4DUUdD3yIsxx8Wy2O9vPJI8BD8KVbGI2Ou1WM
uF040zT9fBdXQ6MdGGzeMyEstSr/POGxKUAYEY18hKcKctaGxAMZyAcpesqVDNmW
n6vQClCbAkbTCD1mpF1Bn5x8vYlLIhkmuquiXsNV6TILOwACAggAw/zNgbBpOKzX
uR7y69YyC3zhfxNvt9w9h3m44bRQQnMTaq0W2jNZe5LbcerFtuB7Hb87Ys6XH6YV
rMS8xxO4lxR2p1avPW2xe0UjiXColcuVJFf7o7hn6ZuhuqNQE9Os1dfJotpg800c
t9nFgetqhPNtwGYJPNiRGAjx9xTJjxr+Nq1MxyO4nuUE4lmUxiXPmf6t3fKk6+jK
aWxe4uQdqpGbW2DxZM+ApStupz2RQSRU8E6Bu/iRxYrfEAvSjSjhL/rsvDQB6SfA
3sTea7dCy28ADqZOKyFEm4uTvaUtKDFQz25OBOI1AG41/TWBVKR/i7UKTtGLG828
1KXr3afwq4kATAQYEQIADAUCO2fZ2QUbDAAAAAAKCRBo3MJdJvHk6OAOAJ9mTwNQ
0uAP4JlRMiXTdmLPefhlkQCgssSyJwGY7eRehF7jSPRcQi88CGo=
=KB4X
-----END PGP PUBLIC KEY BLOCK-----

Venona

'Venona' was the code name for US decrypts made on Soviet traffic, some of which were encoded using a One Time Pad. The codename in the UK was 'Bride' If used correctly, a One Time Pad is unbreakable. The Soviets knew this, and used One Time Pads for much of their encryptions, for trade and diplomatic messages as well as covert traffic.

So, how was it possible for the messages to be broken?

The Soviets had a difficulty, and that was key distribution. They needed to generate and distribute a large amount of random data. This data had to be kept secure as it was distributed to their embassies and agents. This was a monumental task.

They cheated.

They reused some keys on different 'channels' of communication, hoping that nobody would notice. Meredith Gardner was able to combine ciphertexts and remove the effect of the randomising key, in much the same way that the German Lorenz machine was first analysed. This allows the cryptanalysts to guess at letters on one message which used a particular key and try to find guesses which 'made sense' in the other message.

Not all of the traffic was encoded with One Time Pads, though. Over time. Using a variety of methods ranging from defections to buggings and burglaries, more Soviet traffic was decrypted.

The programme ceased in 1980, having started in the 40s. In the 1990s, Venona decrypts were released to the public in several batches and are available for download.

Note that there are, at this time, HTML errors in some links on the Venona webpages. Some links refer to things like: http://localhost/venona/venon00026.cfm

To fix this, just copy the link, paste it into the address bar, and replace 'localhost' with www.nsa.gov, so the above becomes: http://www.nsa.gov/venona/venon00026.cfm

Using Spruchnummer to crack Lorenz

Before reading further, you may like to read earlier articles on XOR and the Spruchnummer error. In sending the Lorenz cipher, one German operator used the same settings to send two identical messages, or rather, near identical messages. One began 'Spruchnummer' and the other began 'Spruchnr' and continued on.

The allies realised that these two messages used the same key and so they could 'remove the randomness' of the key by XORing the messages together.

When they XORed, they had two plaintexts XORed, the result was gibberish.

Tiltman, then used a 'known plaintext' attack. He guessed some plausible beginnings to the messages, and from experience with Enigma traffic soon guessed that one of the messages would begin 'Spruchnummer' (message number).

He knew his guess was likely to be correct, as XORing 'Spruchnummer' with the start of the message combination, produced a reasonable looking fragment of the second message:

The second message was 'Spruchnrabcd' (where abcd represents the continuation of the second message)

Tiltman then assumed that one message was an abbreviation of the other, so he now guessed the first message was Spruchnummerabcd, this allowed a few more letters of the second message to be found.

He continued in this way through the messages until he was able to decode both messages (the end of the longer message was found as it was an unabbreviated version of the second!) A few times he stalled due to a typing mistake on the part of the German operator, but he could always find a way past the block by trial and error, knowing that the two messages were fundamentally similar.

Now Tiltman had plaintexts and ciphertexts, so he was able to extract the string of key bits which was used. He looked at the behaviour of each of the bits in the key (i.e. the first bit in each character, the second bit and so on), and was able to extract periodically repeating information. This allowed him to deduce the internal structure of the machine. The machine settings would change with each message, but now he knew how the machine did what it did.

This was all a real Tour de force.

More fun with XOR

In order to discuss how the 'Spruchnummer' mistake lead the the Lorenz being broken, and why we must never reuse a one time pad key, we must first understand a little more about the nature of the XOR operation. XOR is essentially a 'bitwise' operation, i.e. it operates on signal bits at a time. I've already discussed some of these ideas in the 'One Time Pad' article, this article presents things in a slightly different way, and takes things a little further.

Suppose we had two bits, A and B which are XORed. The bits can only have one of two values, 0 or 1. XOR simply says 'If the bits are the same, the result is zero, if different the result is 1'. Throughout this entry I'll use ⊕ as the symbol for 'XOR'.

Thus, XOR is also 'commutative' (the order it's done in doesn't matter) as 0⊕1 gives the same result as 1⊕0.

Also, if we XOR anything with 0, the result is the same as whatever we put in (1⊕0=1 and 0⊕0=0).

Now, imagine that we have a set of plaintext bits, P, that we wish to combine with a set of key bits, K.

The result is ciphertext, C, where C=P⊕K.

To get to P, we just do C⊕K, i.e. XOR undoes itself. You should see that K⊕K=0, this is because each bit is being XORed with an identical copy of itself.

To see this, we'll start by saying that C = P⊕K, as above. Suppose we do the operation C⊕K, this is like doing (P⊕K)⊕K. As the order we do things doesn't matter, this is the same as P⊕(K⊕K). As K⊕K = 0, we find that this is P⊕0, which is P!

If you don't believe me, work it through for yourself with some of the previous examples that I used in earlier articles.

Now, suppose that we had two messages, P1 and P2, which are both XORed with the same key, K.

These produce C1 and C2, where C1=P1⊕K and C2=P2⊕K.

We, as cryptanalysts could compute A new message, C1⊕C2. This effectively removes the random key.

This is because C1⊕C2 is equal to (P1⊕K)⊕(P2⊕K).

Rearranging shows this is P1⊕P2⊕K⊕K, and as K⊕K is 0, we get P1⊕P2⊕0, which is just the same as P1⊕P2.

What we are left with is still unintelligable, but we know know that it is one real message XORed with another real message - we have sucked out the randomness, because the same randomness was used twice.

In the second world war, Tiltman used this 'removal of randomness' as a first step in cracking Lorenz.

Protocols for Public Key Systems

PGP Lock

An issue arises with standard cryptography regarding key exchange. Imagine: Two people who cannot meet wish to encrypt a communication. With 'symmetrical' cryptography this cannot be done as they must first agree a key with which they can encrypt their data.

They must agree a key securely, i.e. without eavesdroppers, if their message is to be secure. If they can do this then surely they don't need to use cryptography in the first place!

There are two solutions to this which I am aware of, one is quantum cryptography and the other is public key cryptography. Here we'll discuss the latter.

A public key system addresses this issue by using two keys.

These keys are the public and the private key. The public key is published widely.

The public key can be used by anyone to "lock up" the message, but it will not decode the message - only the private key will do that, and of course, the private key is kept just that - private. (Unless one is using Key escrow!)

There are many ways to produce such a key pair, sufficed to say that the detailed method is not important when discussing how the keys are used. Functions which could be used in this way are called 'trapdoor' functions, as they are easy to use in one direction (e.g. from the private key to calculate the public key) but hard to use in the other.

Let's talk about Alice, Bob and Carol, the cryptographer's stooges. Alice and Bob wish to establish secure communications without having met each other, but Carol is trying to listen in. Can they talk securely?

In a single key system Alice and Bob first have to agree on a key. Carol will simply record the key it is exchanged, and thereafter be able to decode all messages with ease. Clearly this will not be sufficient if the correspondants cannot meet.

Can a public key system solve this dilemma? In the present form the answer is NO. This is not immediately transparent and so I will work through it with you.

 
Alice and Bob make their keys

Alice and Bob both generate a key pair, public and private key. The private key is not revealed, but the public key (shown) is made available for distribution.

Remember, at no point do either disclose their private key.

Alice and Bob exchange keys

Alice and Bob then exchange public keys. . .

Carol takes a Copy

. . . and of course, Carol takes a copy of each key.

 

Surely this is secure? These are public keys remember - they can only be used to encipher information - they cannot be used to decipher the information - only the private key can do that.

Carol cannot read the traffic . . . but have we missed something?

Predictably, Yes we have.

What if Carol is in a position where she can intercept and replace the communication, i.e. what if Carol is, for example, an internet service provider - where all email goes en route through her machine? Then we have a problem.

Carol can replace the keys.

If Carol is in a position where the email goes through her machine then when Alice sends her public key to Bob, Carol could substitute her own key which claims to belong to Alice. Similarly, when Bob sends his key to Alice then Carol simply substitutes a fake "Bob key".

The situation now is that Alice has her real key pair, and a key which she believes belongs to Bob. Bob has his key pair, and a fake Alice key. Carol has the real public keys for Alice and Bob, the fake public keys for Alice and Bob, and also the private keys which correspond to the fake keys.

What happens now when Alice sends a message to Bob?

Well, Alice composes and codes her message as usual. Except now she code it with the faked key which Carol slipped to her. Alice then sends the message. Carol can set up software to automatically intercept the email from Alice, and decrypt it - remember she possesses a private key which corresponds to the fake public key of Bob's.

Having read the message, Carol can the re-encipher the message using Bob's real public key and forward the message to Bob as usual. Thus Alice and Bob think they're having a secure conversation, yet in reality Carol is listening in - and she doesn't have the real private keys for either Bob or Alice!

Plugging the Loophole

As we have seen, the main weakness in a public key system is this:
How do I know that this key really belongs to my correspondant?

Protocols have been derived to answer this question. Let's examine several examples.

The most trivial case is the one where the correspondants have had an opportunity to meet, and they've handed over a copy of their keys on floppy disk. They can each be sure that the keys belong to the other person. Obviously, if it is possible to do this then it is surely a good method of knowing that a key may be trusted, however, it is not always practical - otherwise why use Public Key?

This may strike you as being rather cumbersome. It is. This is why key fingerprints were devised. The fingerprint is analagous to a human fingerprint - it's extremely unlikely that two keys will share the same fingerprint.

If Alice and Bob meet then they can exchange key fingerprints, these may be handily printed onto a slip of paper or business card and carried on the person. When Alice and Bob get back home they can simply compare the fingerprint on the piece of paper with the fingerprint of the key under suspicion. Carol's fake keys will bear a different fingerprint, and hence will not be used by Alice or Bob. The fake keys are revealed for what they are.

Of course, if Alice and Bob know each other well enough to talk to over the telephone, then the fingerprint may be read out over the phone.

What if Alice and Bob have never met, and are never likely to meet? This is where key signatures come in.

If you have personally verified that a given key belongs to a given person, then it is common practice to sign that key. The signature is made with your private key - so only you can make the signature - your signature may be verified by anybody, comparing the signature with your public key.

Now suppose Alice and Bob have a mutual friend, David. David has signed both Alice's key and Bob's key, and both Alice and Bob have a verified copy of David's key.

When Bob examines Alice's key he observes that her key was signed by David, Bob trusts that David is reliable when it comes to signing other people's keys. Therefore Bob can be fairly certain that the key belongs to Alice.

The thing with PGP in particular is that YOU decide who is trustworthy when it comes to keysigning.

For instance, it could be that David signs any old key without really verifying the key (as described above) - or it could be that David's private key doesn't belong to David at all. In these cases you'd mark David's key as being "untrustworthy" and his signature would carry no weight.

In this way, by verifying and signing keys wherever possible a "web of trust" may be built up. With trusted keys vouching for new keys. Of course, the weak point is now that person who signs a key without justification - this is why PGP is configurable to allow the user to say how much they trust a key's owner to sign other keys, how many valid signatures are required for a valid key, etc.

Remember, when someone signs a key they are not saying "I believe that this person is a good and trustworthy soul", they are simply saying "I have good evidence that this key belongs to the person whose name is attached to the key".

So if you cannot get any signatures, don't take it as a personal snub, simply supply better evidence as to your identity!