Multiplying large numbers(not OS related)

[pranavappu007]

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.

I read that RSA is using 4096 or 8192 bit key length. That means the the multiplied value and the exponent value combined should be at most 4096 bits long, right? Let's assume that a 1000 digit integer fit inside this key length. To get that, let's assume 2 500 digit numbers are multiplied.

Here is what I can't understand. A 500 digit number should be, like 2000 bits long, right? A modern computer is 64-bit long. A high performance server can be 128 or even 256 bit long. But 2000 bits? I have never heard of any computer capable of or having ALU that can handle that.

So how multiplication, modulo and other operations are being done on that huge numbers? Or RSA is designed not to actually do the calculation this big(because I don't understand it clearly enough)? Or is it just not possible to do that in ordinary computers, and the keys we use are pre calculated?

Or should I just accept cryptography is hard and leave it?

[PeterX]

Cryptography indeed is hard to understand. But it is interesting anyway.

Yes, it is very mathematical.

There are libraries for multiplying large numbers.

Here is a link for multiplying large numbers in Assembler:
https://www.zeepedia.com/read.php?manip ... ng&b=5&c=4
(I don't know if that is interesting for you.)

Greetings
Peter

[Schol-R-LEA]

You are correct in thinking that no mainstream computer has a native integer word that wide. However, this just means that this multiple-precision (or 'bignum') arithmetic has to be done in software.

I am not personally familiar with the algorithmic approaches to Big Integer (or the related Big Decimal and Big Float) arithmetic, or even the more common data structures used for it. One model I know of is called 'Humbers' (Huge Numbers) which work similar to the old Pascal-style strings - a byte (or in newer versions, a 64-bit word) holding a size in bytes, followed by a dynamically allocated array of bytes. Just how you would add, subtract, multiply, and divide is something I've never worked out the details of, personally.

Fortunately, there are mainstream libraries for this, and several languages either use BigNums by default (Python, Ruby, most Lisps) or have standard libraries for them (Java, Rust I think). The most commonly-used library for BigNums is called GMP (GNU Multiple Precision Arithmetic Library).

I have long meant to implement my own BigNum library, but as with most things, all of my projects are so intertwined that I can't un-knot any one of them enough to make progress.

[pranavappu007]

My idea was to implement RSA key generator and encryptor in C(as it is the language I'm most familiar with). I think I misunderstood the hardness of the problem in the first place.

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?

Now that RSA and the underlying BigInt math is too hard, is there any easier asymmetric encryption algorithm that one can actually implement?(Of course it doesn't need to be as secure)

[pranavappu007]

Here is a link for multiplying large numbers in Assembler:
https://www.zeepedia.com/read.php?manip ... ng&b=5&c=4
(I don't know if that is interesting for you.)

Greetings
Peter

Sorry I couldn't get it working on C. I have no idea about how to do it in assembler. Maybe in future if I finally get the idea.

[nullplan]

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.

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.

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.

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.

[PeterX]

My idea was to implement RSA key generator and encryptor in C(as it is the language I'm most familiar with). I think I misunderstood the hardness of the problem in the first place.

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?

Now that RSA and the underlying BigInt math is too hard, is there any easier asymmetric encryption algorithm that one can actually implement?(Of course it doesn't need to be as secure)

No, it doesn't get easier. Without big integers and modulo operations you won't get far in asymetric encryption.

You don't have to understand WHY the algorithm works. I had specialization in math back in school. Still I have a hard time to understand the mathematical proof that the algorithm "works". You just have to understand the algorithm itself well.

(Note that on the far horizon are potentially quantum-computers. If they ever get inplemented, normal asymetric encryption can be cracked easily. The remedy is lattice crypto.)

Greetings
Peter

[Solar]

Now that RSA and the underlying BigInt math is too hard...

You will need BigInt at various other places as well, including floating point support for printf(). (Which is why I am engaged in the subject ATM.)

However, cryptographic BigInt is much harder even than "normal" BigInt. There are various ways to attack a poor implementation by measuring how long it takes for a given operation, or how much memory it used, because that allows to reduce the number of guesses it takes to break the cipher. That is one of the reasons why it is strongly discouraged to try a cryptographic implementation yourself. (And why I promiently labeled my own BigInt support code to be not fit for cryptographic purposes.)

Just don't do it. Take one of the available (and peer-reviewed) implementations and port it. Otherwise you will feel secure but won't be.

[pranavappu007]

Just don't do it. Take one of the available (and peer-reviewed) implementations and port it. Otherwise you will feel secure but won't be.

I am not going to encrypt all my passwords and bank account details with this and carry it through internet, it's obvious that my one man hobby implementation is nowhere is secure as a standard implementation by actual computer scientists. I'm not going to implement it anyway useful.

I just want to know how the idea of asymmetric idea of RSA works out by actually implementing some version of it. As of now, I think I technically know the theory of RSA, and something from BigInt by using school algorithm for multiplication. I might not be fast, it might not be secure, but it works(maybe). Still has to go a long way to have a barely working RSA key generator. Let alone encryptor and decryptor.

As I have mentioned in my last post, I am also looking for other implementations of Asymmetric. But the replies suggest RSA is the easiest(my god..).

[pranavappu007]

No, it doesn't get easier. Without big integers and modulo operations you won't get far in asymetric encryption.

You don't have to understand WHY the algorithm works. I had specialization in math back in school. Still I have a hard time to understand the mathematical proof that the algorithm "works". You just have to understand the algorithm itself well.

Greetings
Peter

I can't even understand how the algorithm works(as I can't make it work) let alone why it work. I mean I know the theory that you do some strange calculation large number exponents and modulos and you have the inverse number of that exponent number to 'decrypt' the number.

Also I know Big Int arithmetic is basically just the human way of doing arithmetic but with more than single digit. But still can't just go ahead and implement it. I kinda made it work with single digit multiplication but it's full of bugs.

[PeterX]

I can't even understand how the algorithm works(as I can't make it work) let alone why it work. I mean I know the theory that you do some strange calculation large number exponents and modulos and you have the inverse number of that exponent number to 'decrypt' the number.

Also I know Big Int arithmetic is basically just the human way of doing arithmetic but with more than single digit. But still can't just go ahead and implement it. I kinda made it work with single digit multiplication but it's full of bugs.

If that is true (and only then) I would indeed give the advice you mentioned earlier: Crypto math is hard. Don't waste your time with it.
But I think you _could_ learn it if you _really_ want to, as nullplan said.

Greetings
Peter

[Solar]

Also I know Big Int arithmetic is basically just the human way of doing arithmetic but with more than single digit.

Indeed. (With the notable exception of division, which is inefficient to implement that way.)

Let's have a look at how we would implement plain old decimal arithmetics if we had to store each digit individually. (Let's ignore negative numbers for the moment, because we can.)

A decimal number is simply an array of digits (d) with values in the 0..9 range.

Code: Select all

struct number
{
    unsigned * d;
    size_t size;
};

Let's store the least significant digit at d[0]. The base (b) of this number is 10, each digit in the range of 0..(b-1). The value of each digit is (d[x] * b^x), with the sum of each individual value being the number.

Now let's have a look at basic arithmetics on two such numbers, x and y. The smaller number is that with the shorter size, or (if sizes are equal) the smaller d[size - 1].

• Addition: Starting at index 0, add the two digits at that index plus any carry from the previous loop. (If a number has no digit at that index, use zero instead.) If that sum would be larger than b, take the result modulo b, and let carry be one. Else, let carry be zero. Repeat until you run out of digits in the smaller number and your carry is zero.
• Subtraction: Starting at index 0, substract the digit at that index of the smaller number (plus any carry from the previous loop) from the digit of the larger number. If that would result in a negative, wrap the result arount, and let carry be one. Else, let carry be zero. Repeat until you run out of digits in the smaller number and your carry is zero.

Those two are very simple, and can actually be done in-place -- you can write back the result directly into the larger number. Carry is either 1 or 0.

Multiplication is trickier; you need to handle an intermediary result with twice the width of your base (9 x 9 = 81), and (for an iterative implementation) you need two nested loops.

• Multiplication: Loop over the digits of the smaller number, beginning at index s = 0.
  • Loop over the digits of the larger number, beginning at index w = 0.
    • Let the intermediary result be the sum of:
      • The result digit at index [s + w];
      • the product of the digit d of the smaller number and the digit d[w] of the wider number;
      • any carry from the previous loop.
    • Let the carry be the intermediary result divided by base b.
    • Let the result digit at index [s + w] be the remainder of that division.
  • Add the carry to the result digit at index [s + w].

This can be optimized further, but it makes the algorithm much less intuitive.

If you have followed my reasoning so far (this is elementary, after all), turning this into BigInt arithmetics is very, very easy: Instead of using b = 10 and storing 0..9 in each digit, you use b = 2^32 and store 0..(2^32-1) in each digit. The algorithms remain the same. If you don't have a 64bit value for the intermediary mutiplication result, use b = 2^16.

So my suggestion would be, implement and test this on b = 10 (while assuming that your unsigned type can't hold more than 0..9 to get the overflow handling right), and once you're "there", just change the base. Note that my implementation linked above assumes a fixed array size (because I will use it "only" for printing floats, where I know the maximum required size beforehand). Your implementation might need to assign memory dynamically.

As I said before, division is trickier to do with any degree of efficiency (that is the whole point of many encryption schemes), and I haven't fully implemented it yet, so I won't sketch an algorithm here lest I give flawed advice. The basic idea, though, is to approximate a quotient from the highest digits of the operands, and adjust that when (during calculation of the remainder) you find that the approximation was off.

[bzt]

One plus vote on BigInt. OpenSSL has it's own implementation (BN or BIGNUM), which is relatively easy to use https://github.com/openssl/openssl/blob ... /crypto/bn (well, here the meaning of "realively" is relative too).

On x86_32 you could also use BCD numbers, which have hardware support so they are fast and can be any arbitrary length. Those instructions are just as easy to use as binary int's. Sadly BCD was removed from long mode for some unknown reason, but you can still chain up several mul/div etc instructions on carry flag to have a good speed. OpenSSL btw has Assembly implementation for many architectures, and the x86_64 version just does that.

Cheers,
bzt

[eekee]

BCD is very nice for calculators, but it reduces the size of number which can be stored by a given number of bits. It would reduce the effectiveness or increase the size of crypto keys.

I wouldn't be surprised if bigints are much easier in assembly language. For addition and subtraction, you get a carry flag which can be used in the next word with an ADC instruction -- add with carry. ("Word" is the traditional term for a collection of bits without stating the size.) For multiplication, I think just-about every CPU supports multiplying two words to produce a double-word result. Half the result is put in another register. For instance, given 3 registers, A B and C, multiplying A and B puts the lower half of the result in A, the upper half in C. For division, you get an operation which divides a doubleword by a word, giving a single word result. CA divided by B puts the result in A, and maybe a remainder in C. The word size may be anything the CPU supports. I'm pretty sure Intel & AMD support these forms of multiplication and division on word sizes from 8 to 64 bits. (But note that Intel particularly uses "word" to mean 16 bits. It's a little confusing.)

[rdos]

I did a bignum implementation in x86 assembly. As noted, add and sub are rather easy, multiplication and divide are a bit more complex, but not overly. You also need a function to convert to and from human readable format which is a bit like iterated divide by 10. As for encryption, there is a special kind of operation based on exponents and modulo that basically is impossible to do with full precision, and that relies on only keeping the modulo part and iterating over it.