0

I'm trying to write an RSA implementation and need to work with numbers that are 100 bits and larger. Are there any C++ data types that can allow for this?

Maurice Kasomwung
  • 178
  • 1
  • 12
  • Does this answer your question? [Is there a 128 bit integer in C++?](https://stackoverflow.com/questions/18439520/is-there-a-128-bit-integer-in-c) – Jan Schultke Aug 19 '20 at 08:49
  • Most mainstream compilers and platforms have a 128 bit int. If not I'd recommend boost multiprecision. – Bathsheba Aug 19 '20 at 08:57
  • Note that RSA with 512bit keys is crackable now and 1024 potentially by governments. So you should be looking at using 2048 and preferably 4096 bits to give some degree of future proofing. – Richard Critten Aug 19 '20 at 09:30
  • 1
    @RichardCritten: Possibly 2048 too if you can harness the server farm used by the new flight simulator. – Bathsheba Aug 19 '20 at 09:33
  • @Bathsheba I think you vastly underestimate how quickly the work required goes up per bit. For RSA it is not exponential, but it is not linear either. Anyway, for real RSA calculations you need a side channel resistant implementation which is commonly only found in cryptography libraries. That's much more of a likely attack vector after all, especially on shared systems / shared CPU resources or fast NW interfaces. – Maarten Bodewes Aug 19 '20 at 14:05

2 Answers2

3

If by "C++ data type" you mean "primitive integral type guaranteed by the standard", then no.

If by "C++ data type" you mean "primitive integral type that actually exists on my platform", then maybe, but you'd have to tell us what your platform is, and you haven't.

If by "C++ data type" you mean "any type usable in C++", then the answer is trivially of course, since any platform will be able to fit std::array<uint32_t, 4>. You'll have to write some code to use that like a regular integral type, though.

The more general solution is to use a big integer, arbitrary precision or multiprecision library. For example Boost.multiprecision, but you can find lots of others now you know the correct search terms.

Note

Maarten Bodewes makes a good point about security that I completely ignored by just answering the C++ part. You didn't say that your RSA implementation has any security requirements at all, but just in case ...

If you do care about it actually being safe to use in some real application, consider that

  1. 100 bits is probably much too weak, and
  2. you may have more security concerns than just the correctness of the algorithm (such as side-channel attacks and malicious input attacks).

These are well outside the scope of this (or any other individual) question, but they deserve some thought and research. Using a multiprecision library indended specifically for cryptographic use is the minimal first step to getting this right.

Useless
  • 64,155
  • 6
  • 88
  • 132
2

If you've been using GCC and your computer supports 64-bit architecture, you could use __int128_t datatype in C++ to hold 16-bytes of data (i.e. 128-bits integer). As mentioned by @Batsheba, you could rather use the boost multiprecision library (comes along /multiprecision/cpp_int.hpp) in case you're having any trouble in using __int128_t.

Rohan Bari
  • 7,482
  • 3
  • 14
  • 34
  • 1
    Note that g++ doesn't have this type on a 32 bit platform. The good thing about Boost is that it deals with that situation portably. E.g. on a 64 bit platform with g++ it simply typedefs __int128_t. – Bathsheba Aug 19 '20 at 09:11
  • 1
    **Warning**: using a library that is not explicitly written with side channels in mind will probably result in an insecure implementation. – Maarten Bodewes Aug 19 '20 at 14:07