Secure communications in presence of third parties i.e. adversaries is an old age problem and cryptography is the practice and study of techniques to solve this problem.
The history of cryptography can be split into two eras: the classical era and the modern era. In classical era, cryptography was synonymous with encryption – conversion of human readable message into incomprehensible information, such that interceptors cannot make any sense of the communication. A breakthrough was achieved in 1977, when both the RSA algorithm and the Diffie-Hellman key exchange algorithm were introduced and marked the start of modern era. These new algorithms were ground-breaking as they represented the first viable cryptographic schemes where security was based on the number theory enabling for the first time secure communication between adversaries without a shared secret.
In modern era with the advent of emerging technologies like Blockchain, cryptography has much more to offer than just encryption in the form of integrity, authentication, and digital signatures, interactive proofs and secure computations. Modern cryptography is founded on the idea that the key that you use to encrypt your data can be made public while the key that is used to decrypt your data can be kept private i.e. Encryption with the public key can only be undone by decrypting with the private key. The public keys are generated by transforming private key through a one-way function that is easy to calculate in one direction and difficult in o
ther. The whole security of modern communication depends on the “hardness” of this one-way function. Here the word hardness represents the computational complexity i.e. time taken to compute one key from another. In theory it should be very easy and computationally cheap to calculate public key from private key but impossible or computationally very intensive to calculate private from public. As such, these systems are known as public key cryptographic systems.
The first, and still most widely used of these systems, is known as RSA—made up of the initial letters of the surnames of Ron Rivest, Adi Shamir, and Leonard Adleman, who first publicly described the algorithm in 1977 and it uses factorization.
Integer factorization is the process of determining which prime numbers divide a given positive integer. Computers don’t do well with arbitrary large numbers so in factorization it is important to ensure that the numbers do not get too large by choosing a maximum number and only dealing with numbers less than the maximum. Any calculation that results in a number larger than the maximum gets wrapped back to a number in the valid range. In RSA, this maximum value (max) is obtained by multiplying two random prime numbers. The public and private keys are two specially chosen numbers that are greater than zero and less than the maximum value (say pub and priv). To encrypt a number, you multiply it by itself pub times, it needs to be wrapped around whenever it hits the max. To decrypt a message, it just needs to be multiplied by itself priv times, to get back to the original number.
It works like magic, let’s try to encrypt and decrypt word CITI using this technique.
Take the prime numbers 13 and 7. Their product gives maximum value of 91. Let’s assign the public encryption key to be the number 5. Then using the fact that we know 13 and 7 are the factors of 91 and applying an algorithm called the Extended Euclidean Algorithm, the private key can be deduced as the number 29. These parameters (max: 91, pub: 5, priv: 29) define a fully functional RSA system. You can take a number and multiply it by itself 5 times to encrypt it and then take that encrypted number and multiply it by itself 29 times and you get the original number back.
In case of CITI, to represent it mathematically, let’s first turn the letters into numbers. A common representation of the Latin alphabet is UTF-8. Each character corresponds to a number.
So CITI can be represented mathematically as 67 73 84 73.
To start with letter C, as it is number 67 on UTF-8, let’s multiply 67 by itself five times to get the encrypted value for C.
67×67 = 4489
Since 4489 is larger than max i.e. 91, it needs to be wrapped around. This can be done by dividing by 91 and taking the remainder i.e. 4489 = 91×49 + 30
30×67 = 2010 = 8
8×67 = 536 = 81
81×67 = 5427 = 58
This means the encrypted version of 67 (or ‘C’) is 58. Similar calculation for rest of the letters would give ‘I’ = 47, ‘T’ = 28, ‘I’ = 47
Hence the encrypted value for CITI becomes 58 47 28 47.
Now let’s see how decryption works.
To decrypt each encrypted value it needs to be multiplied by itself 29 times. Again starting with C, the encrypted value for C is 58, so this needs to be divided by itself 29 times and if exceeds max then needs to be wrapped around.
58×58 = 3364 = 88 (Remember, we wrap around when the number is greater than max.)
88×58 = 5104 = 8
… (Repeated in total 29 times)
9×58 = 522 = 67
There you’re, back to 67. Similarly we get back 73 for ‘I’, 84 for ‘T’ and 73 for ‘I’ again.
And CITI gets decrypted back to original UTF-8 representation as 67 73 84 73.
Though factorization provides rigorous security proofs yet it is not a hardest problem on a bit by bit basis. Due to recent advancements in cryptanalysis, it has become very easy to factor keys which were previously thought secure. To counter this simple fix cryptographers have come up with is just to increase the bit size of the keys. Since the resources available to decrypt numbers are increasing, the size of the keys needs to grow even faster. This is not a sustainable situation for mobile and low-powered devices that have limited computational power. The gap between factoring and multiplying is not sustainable in the long term.
In 1985, new types of cryptographic algorithms were proposed based on an esoteric branch of mathematics called elliptic curves.
Elliptical Curve is what most common browsers use today to secure the communication. An elliptic curve is the set of points that satisfy a specific mathematical equation. The equation for an elliptic curve looks something like this:
y
2
= x
3
+ ax + b
The property of elliptic curves that makes it interesting for cryptography is the horizontal symmetry of these graphs. Any point on the curve can be reflected over the x-axis and remain the same curve. Another more interesting property is that any non-vertical line will intersect the curve in at most three places.
Take any two points on the curve and draw a line through them; the line will intersect the curve at exactly one more place. In elliptical curve systems, we start with our private key (q) and a well-defined point (p) on the curve. Then we find the point (p*q) on the curve. That point is defined as public key corresponding to the private key. On elliptical curves it turns out that if you have two points, an initial point “dotted” with itself n times to arrive at a final point, finding out n when you only know the final point and the first point is hard. The mathematics works out in such a way that all rational multiples of p also ends up being on the curve. The claim is that it is very easy on elliptical curves to derive the public key by multiplication but computationally hard to find the reverse i.e. private from public.
After a slow start, elliptic curve based algorithms are gaining popularity, and the pace of adoption is accelerating. Elliptic Curve Cryptography (ECC) is now used in a wide variety of applications: the US government uses it to protect internal communications; the Tor project uses it to help assure anonymity, it is the mechanism used to prove ownership of bitcoins, and it provides signatures in Apple’s iMessage service. First generation cryptographic algorithms like RSA and Diffie-Hellman are still the norm in most arenas, but ECC is quickly becoming the go-to solution for privacy and security online.
Tarun Rattan
Credits: Nick Sullivan
Tarun's Blog 