本文實(shí)例講述了Python 25行代碼實(shí)現(xiàn)的RSA算法。分享給大家供大家參考，具體如下：

網(wǎng)絡(luò)上很多關(guān)于RSA算法的原理介紹，但是翻來翻去就是沒有一個(gè)靠譜的算法實(shí)現(xiàn)，即使有代碼介紹，也都是直接調(diào)用JDK或者Python代碼包中的API實(shí)現(xiàn)，或者即使有代碼也都寫得特別爛。無形中讓人感覺RSA加密算法竟然這么高深，然后就看不下去了。還有我發(fā)現(xiàn)對(duì)于“大整數(shù)的冪次乘方取模”竟然采用直接計(jì)算的冪次的值，再取模，類似于(2 ^ 1024) ^ (2 ^ 1024)，這樣的計(jì)算就直接去計(jì)算了，我不知道各位博主有沒有運(yùn)行他們的代碼？？？知道這個(gè)數(shù)字有多大嗎？這么說吧，把全宇宙中的物質(zhì)都做成硬盤都放不下，更何況你的512內(nèi)存的電腦。所以我說他們的代碼只可遠(yuǎn)觀而不可褻玩已。

于是我用了2天時(shí)間，沒有去參考網(wǎng)上的代碼重新開始把RSA算法的代碼完全實(shí)現(xiàn)了一遍以后發(fā)現(xiàn)代碼竟然這么少，25行就全部搞定。為了方便整數(shù)的計(jì)算，我使用了Python語言。為什么用Python？因?yàn)镻ython在數(shù)值計(jì)算上比較直觀，而Java語言需要用到BigInteger類，數(shù)值的計(jì)算都是用方法調(diào)用，所以使用起來比較麻煩。如果有同學(xué)對(duì)我得代碼感興趣的話，先二話不說，不管3X7=22，把代碼粘貼進(jìn)pydev中運(yùn)行一遍，是驢是馬拉出來溜溜。看不懂可以私信我，我就把代碼具體講講，如果本文章沒有人感興趣，我就不做講解了。

RSA算法的步驟主要有以下幾個(gè)步驟：

①、選擇 p、q兩個(gè)超級(jí)大的質(zhì)數(shù)
②、令n = p * q。取 φ(n) =(p-1) * (q-1)。
③、取 e ∈ 1 < e < φ(n) ，( n , e )為公鑰對(duì)
④、令 ed mod φ(n) = 1，取得d，( n , d ) 為私鑰對(duì)。 利用擴(kuò)展歐幾里的算法進(jìn)行計(jì)算。
⑤、銷毀 p、q。密文 = 明文 ^ e mod n ， 明文 = 密文 ^ d mod n。利用蒙哥馬利方法進(jìn)行計(jì)算

代碼主要涉及到三個(gè)Python可執(zhí)行文件：計(jì)算最大公約數(shù)、大整數(shù)冪取模算法、公鑰私鑰生成及加解密。這三個(gè)文件構(gòu)成了RSA算法的核心。

前方高能，我要開始裝逼了。看不懂的童鞋請(qǐng)繞道，先去看看理論，具體內(nèi)容如下：

1. 計(jì)算最大公約數(shù)
2. 超大整數(shù)的超大整數(shù)次冪取超大整數(shù)模算法（好拗口，哈哈，不拗口一點(diǎn)就顯示不出這個(gè)算法的超級(jí)牛逼之處）
3. 公鑰私鑰生成

1、計(jì)算最大公約數(shù)與擴(kuò)展歐幾里得算法

gcd.py文件，gcd方法用來計(jì)算兩個(gè)整數(shù)的最大公約數(shù)。ext_gcd是擴(kuò)展歐幾里得方法的計(jì)算公式。

# -*- coding: utf-8 -*-# 求兩個(gè)數(shù)字的最大公約數(shù)（歐幾里得算法）def gcd(a, b):  if b == 0:    return a  else:    return gcd(b, a % b)'''擴(kuò)展歐幾里的算法計(jì)算 ax + by = 1中的x與y的整數(shù)解（a與b互質(zhì)）'''def ext_gcd(a, b):  if b == 0:    x1 = 1    y1 = 0    x = x1    y = y1    r = a    return r, x, y  else:    r, x1, y1 = ext_gcd(b, a % b)    x = y1    y = x1 - a / b * y1    return r, x, y