实现rsa加密的bignum库 [英] implementing a bignum library for rsa encryption

问题描述

所以我当然知道有简单的解决方案，如使用GMP库或许多其他任意精度库。这是为了工作，所以我不允许采取任何这些路线。在我们建立了所有的操作之后，我们正在进行一个RSA加密方案。

So of course I know there are simple solutions to this such as using the GMP library or numerous other arbitrary-precision libraries. This is for class work so I am not allowed to take any of these routes. After we build up all our operations we are leading up to be able to do a RSA encryption scheme.

我使用向量来存储以二进制表示的n位数字。我已经转换为十进制，但我必须对二进制操作，并且只转换为显示。

I am using vectors to store n-bit numbers represented in binary. I have conversions to decimal later but I must operate on the binary and only convert for display.

我已经成功实现了加法，减法和乘法。我坚持分裂和模块化操作...特别是模幂运算。我理解算法至少在基本水平，但似乎无法将其转换为代码，将工作在任意长度的数字。我不能在没有外部库的情况下找到这种类型的工作的例子。

I have successfully implemented addition, subtraction, and multiplication. I am stuck on division and modular operations... specifically modular exponentiation. I understand the algorithms at least at a basic level but cant seem to translate it into code that will work on arbitrary length numbers. I cant seem to find any examples of this type of work done in c++ without external libraries.

一些具体问题：

是否有更好的方法对n位数执行模数？

is there a better way to do modulus on a n-bit number besides just calling the division function I am writing and using the remainder returned?

喜欢看到一些好的c ++示例，因为我不能遵循GMP源代码。

I really would love to see some good c++ examples as I cant follow the GMP source code well at all.

任何好的资源学习或一些帮助将非常感谢。感谢

Any good resources to study or some help would be greatly appreciated. Thanks

推荐答案

您可以使用除法来模拟运算。您的模数运算等效于：

You can fake modulus operations with division. Your modulus operation is equivalent to:

v = n - (n / m) * m

其中n是除数，m是模数，v是输出值（所有任意精度数）

where n is the divisor, m is the modulus, and v is the output value (all arbitrary precision numbers)

如果你坚持分裂，你可以只是实现它，就像你将用手执行长分裂。 （你应该已经学会了如何在中学通过乘法和减法来做这个过程很容易将过程转换为基础2.如果你卡住，在纸上做几个如果你想要一个更有效的算法，你可能通过在google上搜索诸如任意精度除法算法之类的东西来找到一个）

If you're stuck on division you can just implement it like you would perform long division by hand. (You should have learned how to do this in middle school via multiplication and subtraction. It's easy enough to translate the process to base 2. Do a few on paper if you're stuck. If you want a more efficient algorithm, you can probably find one by searching on google for something like "arbitrary precision division algorithm")

一旦你有了模数，就可以用重复的平方来计算模幂。观察我们计算一些大整数X的权力为67，mod N：

Once you have modulus, you can compute modular exponentiation with repeated squaring. Observe as we compute some large integer X to the power of 67, mod N:

v1  = X mod N         // X^1 mod N
v2  = v1  * v1  mod N // X^2 mod N
v4  = v2  * v2  mod N // X^4 mod N
v8  = v4  * v4  mod N
v16 = v8  * v8  mod N
v32 = v16 * v16 mod N
v64 = v32 * v32 mod N // X^64 mod N

v66 = v64 * v2  mod N // X^66 mod N
v67 = v66 * v1  mod N // X^67 mod N

在数学上，你可以看到为什么这是有道理的。该算法是用于计算模幂运算的通常选择的算法，并且在对数大小和对数大小的基数的时间和空间中操作（即，它是快的，即使对于巨大的数）

Mathematically, you can see why this makes sense. This algorithm is the generally chosen algorithm for computing modular exponentiations, and operates in time and space logarithmic to the size of the exponent and logarithmic to the size of the base (i.e. it's fast, even for huge numbers)

PS确保你告诉你的教授，他愚蠢的不让你使用外部库。程序员可以学习的最重要的事情之一是何时懒惰（即何时找到并使用库来做某事而不是自己解决自己的解决方案）

P.S. Make sure you tell your professor he's silly for not letting you use external libraries. One of the most important things programmers can learn is when to be lazy (i.e. when to find and use a library to do something rather than homebrewing your own solution)

这篇关于实现rsa加密的bignum库的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！