有些想補(bǔ)充的內(nèi)容，但不好直接在初始的那一篇里改。因?yàn)槟抢镏v得太細(xì)致了，是一步步講得，要想再塞點(diǎn)別的東西進(jìn)去就雜亂無(wú)章或喧賓奪主了。。所以重開(kāi)一篇，后續(xù)有什么問(wèn)題，都在這里更新。不是說(shuō)細(xì)節(jié)我都明白透了（畢竟我也沒(méi)實(shí)際寫過(guò)RSA，只看過(guò)別人寫的...看的還不仔細(xì)），只是自己懂一點(diǎn)也可以記錄一點(diǎn)，順便和大家分享。

背景就說(shuō)到這，下面是我自己想補(bǔ)充的內(nèi)容！

=================================

在第一篇中，從問(wèn)題的起因，到尋求解決的步驟，是一步步沿著設(shè)計(jì)者的足跡，得到了算法的實(shí)現(xiàn)。每一步都尋求解決一個(gè)問(wèn)題，很自然地到達(dá)最終的結(jié)果。這樣順?biāo)浦鄣刈?#xff0c;也許比較輕松，但可能走到最后，便忘記了開(kāi)始，沒(méi)辦法一覽順流而下的整條河的概貌。

這里，我想僅就算法實(shí)現(xiàn)，再梳理一下步驟。

前一篇文章中，我粗略描述了蒙哥馬利乘的接口（稍微改一下傳參，BIGNUM還是不好作為返回值...得作為參數(shù)傳進(jìn)去再輸出來(lái)）：

[1] int bn_mont_Mult (BIGNUM Result, BIGNUM A, BIGNUM B, BIGNUM X); 名稱：蒙哥馬利乘 功能：輸出 Result = A * B [* R^(-1) mod X ]

并且在前一篇文章里，實(shí)現(xiàn) A^E mod X 大數(shù)模冪運(yùn)算，寫的是如下（半吊子）代碼：
（在此僅改了傳參規(guī)范）

int bn_PowMod_old (BIGNUM Result, BIGNUM A, BIGNUM E, BIGNUM X){ // Result = pow(A^E) mod XBIGNUM A0, Ret;int K, L;int *a = NULL, *e = NULL;K = bn_Expand(A, 2, a);bn_LShift(A0, A, K); // A0 = A*R, *R 實(shí)現(xiàn)為移位運(yùn)算Ret = A0;L = bn_Expand(E, 2, e);for(int i = L; i >= 0; i--){ // 利用了簡(jiǎn)化冪運(yùn)算的“平方-乘算法”,從高位開(kāi)始bn_mont_Mult(Ret, Ret, Ret, X);if(e[i]==1){bn_mont_Mult(Ret, Ret, A0, X);}}bn_RShift(Ret, Ret, K); // Ret = Ret*R', 移回來(lái)return Ret; }

這段代碼里，有幾個(gè)問(wèn)題：

我寫了一個(gè) bn_LShift 和 bn_RShift 用來(lái)表示“蒙哥馬利變換”和“蒙哥馬利逆變換”，實(shí)際上不會(huì)那么處理。。大數(shù)都是切割成一塊塊的，移位咋移啊。。

可以看到，bn_mont_Mult 里的 R 的長(zhǎng)度（或值），實(shí)際上是依賴于入?yún)?A 的長(zhǎng)度的，也就是說(shuō)并不是一個(gè)寫死的值，所以實(shí)際上需要傳入 A 的長(zhǎng)度。

其實(shí)還有一個(gè)問(wèn)題。。這個(gè)之前沒(méi)有知友看出來(lái)。那就是 Ret 沒(méi)有賦初值 = =。。。好嚴(yán)重的錯(cuò)誤有木有....我的鍋

那么我們?cè)囍囊幌?#xff0c;首先不妨（暫時(shí)）假設(shè)我們相應(yīng)地修改好了接口，并且方便起見(jiàn)，將bn_mont_Mult 相同兩個(gè)大數(shù)相乘的情況封裝為 bn_mont_Square 平方接口，即：

[2.a] int bn_mont_Mult (BIGNUM Result, BIGNUM A, BIGNUM B, uint32_t alen, BIGNUM X); 名稱：蒙哥馬利乘 功能：輸出 Result = A * B [* R^(-1) mod X ], R = 2^(-alen) 備注：在此假設(shè) alen 是 A 的比特長(zhǎng)度[3.b] int bn_set_mont(BIGNUM R, uint32_t alen, BIGNUM X) 名稱：獲取蒙哥馬利參數(shù) R 功能：輸出大數(shù) R = 10000...(alen 個(gè) 0) mod X[2.c] int bn_mont_trans(BIGNUM Result, BIGNUM A, uint32_t alen, BIGNUM X) 名稱：蒙哥馬利變換 功能：輸出 Result = A [* R mod X ][2.d] int bn_mont_inv(BIGNUM Result, BIGNUM A, uint32_t alen, BIGNUM X) 名稱：蒙哥馬利逆變換 功能：輸出 Result = A [* R^(-1) mod X ][2.e] int bn_mont_Square (BIGNUM Result, BIGNUM A, uint32_t alen, BIGNUM X); 名稱：蒙哥馬利平方 功能：輸出 Result = A * A [* R^(-1) mod X ], R = 2^(-alen) 實(shí)現(xiàn)： int bn_mont_Square (BIGNUM Result, BIGNUM A, uint32_t alen, BIGNUM X) {return bn_mont_Mult(Result, A, A, alen, X); }

Ret 的初值應(yīng)該是什么呢？感覺(jué)應(yīng)該是1...但考慮到我們用的是蒙哥馬利乘，也就意味著我們乘任何兩個(gè)數(shù)，進(jìn)了 bn_mont_Mult 接口都會(huì)先除以一個(gè) R；至于普通乘法里乘1，意味著被乘數(shù)的值不變，那么作為輸入蒙哥馬利域的數(shù)，怎樣的數(shù)才滿足：任意一個(gè)數(shù)和它做 bn_mont_Mult 后值不變呢？顯然，R是(唯一)一個(gè)這樣的角色；想起來(lái)也很自然，因?yàn)槊筛珩R利乘相當(dāng)于我們把做乘法的位數(shù)“向右平移”了 R 嘛...那1可不是得“向左平移”個(gè)R，來(lái)把它抵消掉。。廢話不多說(shuō)了，模冪的代碼相應(yīng)可修改為：
(A0 改成 AR 吧...代表A*R)

int bn_PowMod (BIGNUM Result, BIGNUM A, BIGNUM E, BIGNUM X){ // Result = pow(A^E) mod XBIGNUM AR, Ret;int K, L;int *a = NULL, *e = NULL;K = bn_Expand(A, 2, a);bn_mont_trans(AR, A, K, X); // AR = A*R mod X, 變換至蒙哥馬利域bn_set_mont(Ret, K, X); // Ret = R = 10000...(K個(gè)0) mod XL = bn_Expand(E, 2, e);for(int i = L; i >= 0; i--){ // 利用了簡(jiǎn)化冪運(yùn)算的“平方-乘算法”,從高位開(kāi)始bn_mont_Square(Ret, Ret, X);if(e[i]==1){bn_MultMod(Ret, Ret, AR, X);}}bn_mont_inv(Ret, Ret, K); // Ret = Ret*R^(-1) mod X, 由蒙哥馬利域變回return Ret; }

這樣好一些了，至少完整了。。但實(shí)際上還可以精簡(jiǎn)。事實(shí)上 bn_mont_trans 這個(gè)大數(shù)乘法可以也用蒙哥馬利乘代替，好比說(shuō)，我們實(shí)現(xiàn)了如下3.幾的一組接口，而不是2.幾的：

[3.a] int bn_mont_Mult (BIGNUM Result, BIGNUM A, BIGNUM B, uint32_t alen, BIGNUM X); 名稱：蒙哥馬利乘;雙因數(shù) 功能：輸出 Result = A * B [* R^(-1) mod X ], R = 2^(-alen) 備注：在此假設(shè) alen 是 A 的比特長(zhǎng)度[3.b] int bn_set_mont(BIGNUM R, uint32_t alen, BIGNUM X) 名稱：獲取蒙哥馬利參數(shù) R 功能：輸出大數(shù) R = 10000...(alen 個(gè) 0) mod X[3.c] int bn_mont_inv(BIGNUM Result, BIGNUM A, uint32_t alen, BIGNUM X) 名稱：蒙哥馬利逆變換;單因數(shù),相當(dāng)于 B = 1 功能：輸出 Result = A [* R^(-1) mod X ] 實(shí)現(xiàn)： int bn_mont_inv(BIGNUM Result, BIGNUM A, uint32_t alen, BIGNUM X) {BIGNUM one = 1; // 反正就是個(gè)賦值...領(lǐng)會(huì)就好return bn_mont_Mult(Result, A, one, alen, X); }[3.d] int bn_mont_Square (BIGNUM Result, BIGNUM A, uint32_t alen, BIGNUM X); 名稱：蒙哥馬利平方 功能：輸出 Result = A * A [* R^(-1) mod X ], R = 2^(-alen) 實(shí)現(xiàn)： int bn_mont_Square (BIGNUM Result, BIGNUM A, uint32_t alen, BIGNUM X) {return bn_mont_Mult(Result, A, A, alen, X); }

正如前文所述，若調(diào)用蒙哥馬利乘來(lái)實(shí)現(xiàn)使 A 賦值變到蒙哥馬利域上，也就是使 AR = A*R mod X，則除 A 之外的另一個(gè)因數(shù)需為 R^2，即：
bn_mont_Mult (AR, A, R^2, alen, X)
才能使得：
AR = A*R^2 [*R^(-1) mod X]

于是代碼修改為：

int bn_PowMod (BIGNUM Result, BIGNUM A, BIGNUM E, BIGNUM X){ // Result = pow(A^E) mod XBIGNUM AR, Ret, R2;int K, L;int *a = NULL, *e = NULL;K = bn_Expand(A, 2, a);bn_set_mont(R2, 2*K, X); // R2 = 10000...(2*K個(gè)0) mod Xbn_MultMod(AR, A, R2, alen, X); // A0 = A*R^2 [*R^(-1) mod X] = A*R mod Xbn_mont_inv(Ret, R2, K); // Ret = R = R2*R^(-1) mod XL = bn_Expand(E, 2, e);for(int i = L; i >= 0; i--){ // 利用了簡(jiǎn)化冪運(yùn)算的“平方-乘算法”,從高位開(kāi)始bn_mont_Square(Ret, Ret, X);if(e[i]==1){bn_MultMod(Ret, Ret, AR, X);}}bn_mont_inv(Ret, Ret, K); // Ret = Ret*R^(-1) mod X, 由蒙哥馬利域變回return Ret; }

這樣應(yīng)該就比較接近真實(shí)的 RSA 蒙哥馬利模冪的接口實(shí)現(xiàn)了。。至少看那些開(kāi)源代碼應(yīng)該能明白哪一步大體在干啥了。

至于剩下的細(xì)節(jié)，比如說(shuō)，如何保證模乘的因數(shù)比模數(shù)小，具體在哪一步取模，等這些細(xì)節(jié)問(wèn)題日后有機(jī)會(huì)再談吧（其實(shí)目前我也搞不清...主要沒(méi)有需求讓我寫 RSA ...國(guó)際上那么多優(yōu)秀的人優(yōu)化了那么多年，怎么也輪不著自己實(shí)現(xiàn)（哈哈哈...）不過(guò)確實(shí)還是挺有意思的算法，不是嗎？

總結(jié)

以上是生活随笔為你收集整理的c++折线平移算法_RSA笔记-蒙哥马利算法（1）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。