pranavappu007 wrote:I was trying to understand how asymmetric encryption algorithms work. I found out that the most used algorithm is RSA, so I checked how it's works. I actually didn't understand the entire stuff completely, but I know it involves multiplying and modulo operation using astronomical numbers.
Yes. You choose two distinct large prime numbers p and q. Multiply them and you get your modulus. Calculate phi = (p - 1)(q - 1). Choose some e that is coprime to phi. Calculate d such that ed = 1 (mod phi) (you can use the extended Euclidean algorithm to do that). Now publish e and m, they are the public key. d and m are the private key. Write as much other information as you want into the private key (it is private, it is not going to hurt anything). Take care to really delete p, q, phi, and d from memory before logging off.
pranavappu007 wrote:I read that RSA is using 4096 or 8192 bit key length.
That far along already, are we? RSA's security is based on the hardness of factorization. The easiest way to break RSA (if implemented properly) is to factorize the public key. From that, you get your p and q back, and can just perform all the steps the legitimate user can. Turns out, solving factorization is not exponential, it is sub-exponential. That's why RSA key sizes are rising faster than, say, ECC key sizes.
pranavappu007 wrote:So how multiplication, modulo and other operations are being done on that huge numbers?
The same way we humans did it. A 8192-bit number is just a number consisting of 1024 digits of 32-bits each. The computer can handle the 32-bit digits, and there are algorithms to extend math on those digits to infinity and beyond. We humans do the same thing, only with base-10 digits. One algorithm to implement multiplication is the school algorithm. You multiply each pair of digits, shift them appropriately, then add up the partial results. Remember from school?
Code: Select all
123 * 456
---------
492
515
738
-----
55088
=====
You can implement the same thing, only with base-2^32 digits. That takes advantage of the fact that in that case, you can get a 64-bit multiply going on to get the upper half of the result.
Modulo in its simplest form can be even easier. See, division and remainder are essentially the same operation. So the absolute simplest algorithm is:
Code: Select all
quotient := 0
remainder := dividend
while (remainder >= divisor)
quotient++
remainder -= divisor
Obviously this is horrible for small divisors, and you may want to get some shifting action going in that case, but the above will work correctly, and even be decently fast for large divisors.
pranavappu007 wrote:My goal was to understand how asymmetric encryption work, as encrypting with one key and be able to decrypt it with another seemed fantastic. I think I kinda know the RSA algorithm, but not enough to make an actual generator. I still don't know what exactly is the key, and why getting public key from private key is faster, as generating one key from other should be harder, that's the point of RSA, right?
Practical implementations do not implement the textbook version. We actually know quite a lot more about RSA now than we did in 1977. The private key is, by definition, private. So you can put whatever information you want into the private key. Yes, the textbook says to only save M and d, but that is not very practical. So OpenSSL for example will also save e, p, q, p-1, q-1, and phi in there. Why not? You must keep the file secret anyway. But with all that information in the private key file, generating a public key is easy, in fact, no calculation has to be done at all. See, for SSL, the private key and public key are two very different things. The private key only contains all those numbers. The public key also contains information about the key holder (that then becomes the certificate request), and then that request can be signed by an authority, becoming a certificate. For RSA, only the numbers are important, for SSL, they are merely part of the whole thing.
RSA is hard. The textbook implementation is flawed, the various hardening techniques are obscure. For example, textbook RSA is essentially a block cipher (you can only encode messages smaller than M, so you must divide the message into blocks that fit that size). A naive implementation would therefore probably implement the ECB mode on RSA. This leads to the problem that the same block will always encrypt to the same encrypted block. That can be an information leak! Also, if the message m happens to be so small that m^e < M, then decrypting the message is trivial, since the modulus does not come into play at all here, and you're just doing arithmetic on integers at that point. Both of these are ameliorated with padding, and there are standards for how RSA padding should work. There are some versions that deal with random padding, just to make it less likely to have to equal blocks.
Other pitfalls are the choice of p and q. If they are far apart, factorization is easy (the lower the smaller of p and q, the easier), but if they are too close to each other, trying numbers around the root of M is possible. So they can be neither too far apart nor too close together. No idea how you do that with random numbers.
Let me rephrase. Textbook RSA is easy. It is probably the easiest cryptosystem out there. But textbook RSA is only really a finger exercise, it is not a good idea to entrust sensitive information to it. The naive implementation you make will probably be full of side channels, so even if you get to a place where the static results of your encryption are secure, if you put that on the internet, people will still be able to guess your parameters. Crypto is hard.
But don't let that discourage you. The knowledge you lack now is something that can be learned. Humans invented RSA. Humans also invented all those FIPS standards for how to use it. It wasn't aliens from another planet, it wasn't advanced AI, it was humans. So humans can also learn to understand all of that stuff. You can read all the standards for how the information is saved. All the ITU standards are public, so you can just look up what an X.225 certificate is, just by looking up X.225. Wikipedia has some helpful hints towards some of the FIPS and NIST standards for using RSA, and you can read those as well. They really only modify textbook RSA, anyway. You probably won't understand everything overnight, but you can start reading and see how far you get.
