關(guān)于RSA算法本身，就提及一下，它是屬于非對稱密碼體制.
基本的加密方式就如下圖所示：
c為加密后的密文，m為加密前的明文
其中一般會給出公開密鑰n、e的值，這樣根據(jù)規(guī)則，便可以實現(xiàn)加密過程。而題目往往需要進行解密，那么就需要先求解出p、q，隨后再求解出私鑰d。但有時候題目還是友善的，會把p、q值告訴你，看你運氣啦！
那么接下來，主要分成的兩個部分內(nèi)容：
一、求解p、q
首先，我們的題目往往是簡單的，即易于破解的！
可以通過尋找最接近n值的一個數(shù)（a）平方，然后與 n 做差，如果差值剛好是某一個數(shù)（b）的平方數(shù)，那么根據(jù)平方差公式，可獲兩個數(shù)（a+b）以及（a-b），如果碰巧兩個都是素數(shù)的話，好耶，問題解決！
若不行，那么繼續(xù)選擇（a+k）的情況，其中 k =1，2，3...再根據(jù)上述步驟進行分析就得，總會出來的，畢竟考試考得是方法。
詳細的內(nèi)容部分如下圖所示啦：
?二、在步驟一的基礎(chǔ)上，求解密鑰d
這里需要求解的公式就是：
其中??的值我們很容易就能獲得
我們直接來看個例子
例子中，最終求得的d值為1019.
這里我個人認為是分成三個部分來看的，不理解算法本身的話，那就學(xué)會觀察！
左上角運用是是歐幾里得法（即輾轉(zhuǎn)相除），如3200/79=40...60；79/60=1...19等等，可以發(fā)現(xiàn)就是不斷地在讓除數(shù)變成被除數(shù)，讓余數(shù)變成除數(shù)，如此循環(huán)，知道余數(shù)為0.
而右上角的呢，實際上是在將左上角的等式進行轉(zhuǎn)換，以此表示出每一個余數(shù)
好了，有了上述兩個鋪墊，那么就可以看最下面的式子了。
首先原本需要求解的問題中，mod 取余運算后等于1，那么我們就反過來，往回推！
1=19-3*6 其中 3?我們可以用 3=60-19*3 表示，所以原式變成了 1=19-（60-19*3）
補充插曲：等式里面還有3，但不需要再一次代入了，根本原因等會兒說，從反面角度來說，繼續(xù)代入只會無限死循環(huán)。同時，原式中的19 也可以直接代入，只不過也可以集中到接下來的一步在整體代入。
原式中 1=19-（60-19*3），接下來就處理19了，19=79-60*1，所以原式就等于
1=（79-60*1）-（60-（79-60*1）*3）
同理，再代入60，所以原式就等于
1=（79-（3220-79*40）*1） -（（3220-79*40）-（79-3220-79*40）*3）
然后展開就能夠獲得
1=（-25）*3220+1019*79?
轉(zhuǎn)變一下式子，也就是說1019*79/3220=25...1 由此就得到了私鑰d！
好了，復(fù)盤一下，其實前面兩步的鋪墊，在我看來就是在尋找除數(shù)與商之間的乘積關(guān)系，而最后一步，借助的是逆向的思維方式，它在盡力的使1=19-3*6 這個式子不斷回推，回推到尋找得到3220與79之間的關(guān)系，也就是說，回代的目的就是在構(gòu)建3200與79的式子。而之前所提及為什么不需要無限回代3，就是因為3只是個中轉(zhuǎn)站，只要和3220、79能夠構(gòu)建起關(guān)系就可以了。
總結(jié)下來就是，尋找關(guān)系（分解），回推，重新構(gòu)建關(guān)系！
希望能夠幫到各位欸，純粹的算法分析就不放在考試向的內(nèi)容里啦！祝大家考試順利，反正當時自己看懂了就很開森~文章來源：http://www.zghlxwxcb.cn/news/detail-757875.html
?文章來源地址http://www.zghlxwxcb.cn/news/detail-757875.html
到了這里，關(guān)于快樂地談?wù)劊宏P(guān)于RSA算法中求私鑰d的歐幾里得方法（輾轉(zhuǎn)相除法）考試向的欸的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
