我有一个关于处理非常大的数字的问题。我正在尝试运行 RSA 算法，让我们假设我有 512 位数字 d 和 1024 位数字 n。decrypted_word = crypted_word^d mod n，不是吗？但是那些 d 和 n 是非常大的数字！非标准变量类型可以处理我的 512 位数字。到处都写着，那个 rsa 最终需要 512 位素数，但实际上我怎么能对这样的数字执行任何数学运算呢？
还有一个想法。我不能使用额外的库。我用 Java 生成我的素数，使用 BigInteger，但在我的系统上，我只有基本的变量类型，而 STRING256 是最大的。
假设您的最大整数大小是 64 位。在大多数语言中，字符串对于做数学运算没有多大用处，因此请忽略字符串类型。现在选择该大小一半的整数，即 32 位。这些数组可以解释为以 2 32为底的数字的数字。有了这些，你可以做很长的加法和乘法，就像你习惯用 10 进制和纸笔一样。在每个基本步骤中，您结合两个 32 位量，以产生 32 位结果和可能的一些进位。如果您在 64 位算术中执行基本操作，您将把这两个作为单个 64 位变量的一部分，然后您必须将其拆分为 32 位结果数字（通过位掩码或简单截断强制转换）和剩余的进位（通过位移）。
分工更难。但是如果除数是已知的，那么你可以通过常数进行除法改为使用乘法。考虑一个例子：除以 7。7 的倒数是 1/7=0.142857…。所以你可以乘以得到相同的结果。显然我们不想在这里做任何浮点数学运算。但是您也可以简单地乘以 14286，然后省略结果的最后六位数字。如果您的股息足够小，这将是完全正确的结果。多么小？好吧，您将 x/7 计算为 x*14286/100000，因此错误将为 x*(14286/100000 - 1/7)=x/350000，因此只要 x<350000，您就安全了。只要您的 RSA 设置中的模数是已知的，即只要密钥对保持不变，您就可以使用这种方法进行整数除法，也可以使用它来计算余数。记得使用基数 2 32但是，而不是以 10 为底，并检查反常数需要多少位数。
您可能需要考虑另一种选择，以便更轻松地进行模减少，即使 n 是可变的。除了将余数表示为数字 0 到 n-1，您还可以使用 2 1024 -n 到 2 1024 -1。因此，如果您的初始数字小于 2 1024 -n，则添加 n 以转换为这种新编码。这样做的好处是您可以在不执行任何除法的情况下执行归约步骤。在此设置中， 2 1024等效于 2 1024 -n，因此基本的模减少将从将某个数字拆分为其较低的 1024 位和较高的其余位开始。较高的其余部分将右移 1024 位（这只是数组索引的更改），然后乘以 21024 -n 最后加到下半部分。在确定结果不超过 1024 位之前，您必须这样做。这取决于 n 的频率，因此对于固定 n，您可以预先计算（对于较大的 n，我希望它是加法后的两个缩减步骤，但乘法后的三个步骤，但请仔细检查）而对于变量 n你必须在运行时检查。最后，您可以回到通常的表示：如果结果不小于 n，则减去 n。如果 n>2 512，所有这些都应该按照描述的那样工作。如果不是，即如果您的模数的最高位为零，那么您可能需要进行进一步的调整。还没有考虑到这一点，因为到目前为止我只将这种方法用于固定模量接近 2 的幂。
现在进行幂运算。我非常建议您为此使用二进制方法。在计算 x d时，您从 x, x 2 =x*x, x 4 =x 2 *x 2 , x 8 =…开始，即计算所有二次幂指数。您还维护一些中间结果，将其初始化为一个。在每一步中，如果在指数 d 中设置了相应的位，则将相应的幂乘以该中间结果。所以假设你有 d=11。然后你会计算 1*x 1 *x 2 *x 8因为 d=11=1+2+8=1011 2. 这样，如果您的指数有 512 位，您最多只需要大约 1024 次乘法。其中一半用于二次幂次方，另一半用于结合二次幂。所有这些中的每一次乘法都应立即进行模减少，以保持较低的内存需求。
请注意，以这种简单的形式，上述求幂过程的速度将取决于 d 中实际设置了多少位。因此，这可能会引发侧信道攻击，这可能使攻击者可以访问有关 d 的信息。但是，如果您担心旁道攻击，那么您真的应该让专家开发您的实现，因为我想可能还有更多我没有想到的那些。
您可以编写一些可以在 Microsoft 下执行的宏，用于诸如 +、-、x、/、模、x 幂 y 之类的函数，这些宏通常适用于小于十或十万位的任何整数（实际的——不是理论上的——限制是 CPU 的内部存储器）。请注意，逻辑与您在小学时得到的逻辑完全相同。
例如：p= 1819181918953471 除数 (2^8091) - 1, q = ((2^8091) - 1)/p, mod(2^8043 ;q) =2332250499585944892976424873521605274650887336316371790204835533676094069761599087158972876550881343466573280403192804544858277594047512683788051964130901866859262253343474518700491839271544287449342544438509371860546124048237126151488670407518661987819423549039620266773342264143625173987712547343719145377235252725006321391676820484493689827863335088666214114196356215718440164746745140403645504333380166689092565960819800928463792369172358980113062314398194823844063569118212154334218709267725967491174440097345403220950235993545743716793731025087600232610173810793063702518395065082177008766020007526686207538313066951913099902992052765623491139242199147175706818774736285414872072892320553434123614649944991089653035972907730036680484643922548308690148420933323659580326331321972546971569954604116292352278417035010458971654452975143943802191472777262039126253410559968860395092332100888317943347489803431828588912911555654147967076104038807535293413732688328724582188899947442100115572156654781397049680955599631385463113749077429756488190187768762817610677191820694543435087350967963810988783193227947063109760401893985578899054262707262604928178415280709765948523883856095831688823813723754859052845089032878008028684403879632510148897798854963952398800282505528646974022784238853875187097169161754314165814231305993432692486784615174977757527931039429656219153060281701454946461425388684383264594686646636295048462955425885571440178547298772784104080581622441365703649995911770124902843519132775727664427294474347929626874982892756555995144194514326965686635521031048223552022058021353342501629899390361575371434345601457747922543591503122586355191160511702939308563294737387263533018171882066983683014731294896.
最后一步耗时约 0.1 秒。
wpjo (willibrord omen on academia.edu)