RSA 的基本原理实现

1.公钥的生成

随机选取两个大的质数 p,q ,相乘得到 n

$n=p*q$

然后计算 n 的欧拉函数

$\varphi(n)=(p-1)*(q-1)$

生成公钥 e
取一个整数 e ,满足以下条件：

$1<e<\varphi(n)$ $gcd(e,\varphi(n))=1$

现在就有了公钥 (n,e)

2.私钥的生成

计算 e 关于 $\varphi(n)$ 的模逆元 d
即：

$e*d\equiv1 \pmod{\varphi(n)}$

有了私钥 (n,d)

3.加密

给定一串明文，转为大整数后计算：

$c=m^{e} \pmod n$

4.解密

计算：

$m=c^{d} \pmod n$

5.原理

$m= c^{d} \pmod n$ $=(m^{e})^{d} \pmod n$ $= m^{ed} \pmod n$ $=m^{k\varphi(n)+1} \pmod n$ $\equiv m \pmod n$

注：

欧拉定理：

$(a,m)=1$ $a^{\varphi(n)} \equiv 1 \pmod n$

费马小定理：
如果 p 是个素数，则：

$a^{p} \equiv a \pmod p$

化简得：

$a^{(p-1)} \equiv 1 \pmod p$

费马小定理为欧拉定理的特殊情况，a 可以为任意整数（ a 不是 p 的倍数）

6.简单攻击方法

1.分解 n ：

得到 p,q ,即可计算 $\varphi(n)$ 和 d

2. p,q 相近：

若 p,q 相近,可以从 $\sqrt{n}$ 开始爆破，从而分解出 p,q 。

3.共模攻击：

条件：

给出互素的 $e_1$ 和 $e_2$, n 相同,对 m 分别加密产生 $c_1$,$c_2$ 。

原理:

$\begin{cases} c_1=m^{e_1} \pmod n \\ c_2=m^{e_2} \pmod n \end{cases}$

因为 $e_1$ 与 $e_2$ 互素，根据贝祖定理有：

$s_1e_1+s_2e_2=1$

找到一组整数解 $(s_1,s_2)$ ,则有：

$(c_1^{s_1}\cdot c_2^{s_2}) \pmod n=((m^{e_1} \mod n)^{s_1} \cdot (m^{e_2})^{s_2}) \pmod n$ $=[(m^{e_1})^{s_1} \cdot (m^{e_2})^{s_2}] \pmod n$ $=(m^{e_1s_1+e_2s_2}) \pmod n$ $=m \pmod n$

从而求解
以下是一个具体解决的例子：

from gmpy2 import *
from Crypto.Util.number import *
n=13060424286033164731705267935214411273739909173486948413518022752305313862238166593214772698793487761875251030423516993519714215306808677724104692474199215119387725741906071553437840256786220484582884693286140537492541093086953005486704542435188521724013251087887351409946184501295224744819621937322469140771245380081663560150133162692174498642474588168444167533621259824640599530052827878558481036155222733986179487577693360697390152370901746112653758338456083440878726007229307830037808681050302990411238666727608253452573696904083133866093791985565118032742893247076947480766837941319251901579605233916076425572961
e1=117
c1=12847007370626420814721007824489512747227554004777043129889885590168327306344216253180822558098466760014640870748287016523828261890262210883613336704768182861075014368378609414255982179769686582365219477657474948548886794807999952780840981021935733984348055642003116386939014004620914273840048061796063413641936754525374790951194617245627213219302958968018227701794987747717299752986500496848787979475798026065928167197152995841747840050028417539459383280735124229789952859434480746623573241061465550303008478730140898740745999035563599134667708753457211761969806278000126462918788457707098665612496454640616155477050
e2 =65537
c2= 6830857661703156598973433617055045803277004274287300997634648800448233655756498070693597839856021431269237565020303935757530559600152306154376778437832503465744084633164767864997303080852153757211172394903940863225981142502888126928982009493972076013486758460894416710122811249903322437742241269681934551237431668187006176418124934488775505816544733929241927900392924886649420943699356314278255683484998359663404611236056664149725644051300950988495549164517140159041907329062655574220869612072289849679613024196448446224406889484578310512232665571188351621585528255501546941332782446448144033997067917984719103068519
s=gcdext(e1,e2)
s1=s[1]
s2=s[2]
print(long_to_bytes(pow(c1,s1,n)*pow(c2,s2,n)%n))

4.共享素数：

条件：

给定具有除1和本身的最大公因数的 n1,n2 ,共同的 e ,以及分别生成的 c1,c2 。

原理：

$gcd(n1,n2)>1$

从而分解出 p,q 。
ex:

from Crypto.Util.number import *
from gmpy2 import *
n1=23220619839642624127208804329329079289273497927351564011985292026254914394833691542552890810511751239656361686073628273309390314881604580204429708461587512500636158161303419916259271078173864800267063540526943181173708108324471815782985626723198144643256432774984884880698594364583949485749575467318173034467846143380574145455195152793742611717169602237969286580028662721065495380192815175057945420182742366791661416822623915523868590710387635935179876275147056396018527260488459333051132720558953142984038635223793992651637708150494964785475065404568844039983381403909341302098773533325080910057845573898984314246089
c1=9700614748413503291260966231863562117502096284616216707445276355274869086619796527618473213422509996843430296526594113572675840559345077344419098900818709577642324900405582499683604786981144099878021784567540654040833912063141709913653416394888766281465200682852378794478801329251224801006820925858507273130504236563822120838520746270280731121442839412258397191963036040553539697846535038841541209050503061001070909725806574230090246041891486506980939294245537252610944799573920844235221096956391095716111629998594075762507345430945523492775915790828078000453705320783486744734994213028476446922815870053311973844961
n2= 22642739016943309717184794898017950186520467348317322177556419830195164079827782890660385734113396507640392461790899249329899658620250506845740531699023854206947331021605746078358967885852989786535093914459120629747240179425838485974008209140597947135295304382318570454491064938082423309363452665886141604328435366646426917928023608108470382196753292656828513681562077468846105122812084765257799070754405638149508107463233633350462138751758913036373169668828888213323429656344812014480962916088695910177763839393954730732312224100718431146133548897031060554005592930347226526561939922660855047026581292571487960929911
c2=20513108670823938405207629835395350087127287494963553421797351726233221750526355985253069487753150978011340115173042210284965521215128799369083065796356395285905154260709263197195828765397189267866348946188652752076472172155755940282615212228370367042435203584159326078238921502151083768908742480756781277358357734545694917591921150127540286087770229112383605858821811640935475859936319249757754722093551370392083736485637225052738864742947137890363135709796410008845576985297696922681043649916650599349320818901512835007050425460872675857974069927846620905981374869166202896905600343223640296138423898703137236463508
e=65537
p=gcd(n1,n2)
q1=n1//p
q2=n2//p
d1=invert(e,(p-1)*(q1-1))
d2=invert(e,(p-1)*(q2-1))
m1=pow(c1,d1,n1)
m2=pow(c2,d2,n2)
print(long_to_bytes(m1))
print(long_to_bytes(m2))

5.低指数加密攻击：

原理：

e 很小

$m^{e}<n$

可以直接求根分解

6.低指数加密广播攻击：

条件：

使用多组公钥且 e 相同( e 也比较小)
即：

$\begin{cases} c_1=m^{e} \pmod {n_1} \\ c_2=m^{e} \pmod {n_2} \\ \qquad \qquad \cdot \\ \qquad \qquad \cdot \\ \qquad \qquad \cdot \\ c_n=m^{e}\pmod {n_n} \end{cases}$

根据中国剩余定理，有通解

$m^{e}= \ \sum_{i=1}^n \ c_i \ t_i \ M_i \mod N$

其中：

$N=n_1 \cdot n_2 \cdot \ldots \cdot n_n$ $M_i=\cfrac{N}{n_i}$ $M_it_i \equiv 1 \pmod n_i$

求出之后对 $m^{e}$ 开方即可
ex:

from gmpy2 import *
from Crypto.Util.number import *
E1=377312346502536339265
ns = [15863230586500684911356384742123404120213699052018048588650392009927565369685497256344682150189923131009586323640507773706997704860898682946308031020361302334248895233255911348365179153799197341744863134926804603973507415697810440916305092395180382239729550833607847524005391137474497849077097574452115379368463540087172800902210822143687014813631366360652583216269138116785489485772437870528892032119729929607857459621078790511144060710035933887337208301078892163837203412081114510143406013892393607932596921308889058909544584619676380766485493114814753878272881866907210235681877689493671668534251778397658670518117, 14144098469438619358682652828507744381697293556670717685553585719665002440476256008471235313826051740009083510860714991201047915737216102220242621674841600987122005914542061963618272275986835928673920375768272390912778741502655909281390948606467847118377641357547931472588836726339758576038273820470879637555458446243401248151675266602656677360819563744765522495640821496694918515669243614141704744848980746101569785439728585144841655665959389460512628800782742764147773150430552859331269667626942993392101897661719871375721143240270211821269260950380944670195863016621594387236339317938305273510719419578308449465183, 27563822879593503938377821960427219022565215631856333510782568496016547757945464794632272818101891677705256471714805217606503652132995136255720639088424576003650628211271025648183600635145895528466199068640094470078526413324708028578289949241288828542143203769199399500669311878391255837977932634772778594526940501234736059441483897017015324765266787399950699732518347518591167932031031320265136158304460199654008895095274754918153773566824931440342525688741289235153882699461549523425169846266597156773535163599640189457171272058311480951820887261040891344076039474315985825984444520336790670313179493074014037981261]
cs = [3833095607830862948079097323254872789586576953317671099752083261949616608759231291050566542764984974722790226120399722937104503590740358249900089784508490830379531632752169777949200718567033018577184658177019404903817920024468923715441355404672443007723525750768430895425376124679225715687382380114628103058312176343693900115638265002657622618744666247132114654135429040069316368839938881716554901593031901272992940200484460436193699175500376368456706998564064693820008778900344357745691652875500810447147088715289581351501876012044611990972521570253106671158207677490849249612002954497927762168699886110455354481924, 1502420121177211156091634258259634977709023894278792755694473756163084431123774101512866316989917922052023168401167212284219907272528117024670443698990238243030221117004372456475521502350404137469088570170885409265567084376069256924135270283335242133163303599239181417949980292944203204296598188175632723968779672994090788585343302473442389865459398142634104331743517384589200789331489394375604801951994831647339839112698394141328178967516636452592385248135340133712522135715943787590172334743893259621909532456281362868290556461907936774231166936915669816509378419892149164552548131776979706381641477878931403040942, 8992204063713908492214256291861339175525948946919629972908439132005643626148678347198381531633907182877152728077958345519083406637446972079387161726967295886447791613166577391233866583354793842121902234644830640050181130381996083089350911224037154798259291124104894554037604500881250119806371348673833105103600782286898276354573884788251542211434143476774391457587885772379990104835187104619922442613860682792470389490804228050671124495925536024571104944112397143299499508504917890140939438891891453283594000764399193028606955089853654071198909973555844004685149713774167524224100487937899126480545681565581673958854]
e = 89
N = 1
for n in ns:
    N *= n
Ms=[]
for n in ns:
    Ms.append(N//n)
ts=[]
for i in range(len(Ms)):
    ts.append(inverse(Ms[i],ns[i]))
sum=0
for i in range(len(cs)):
    sum =(sum+cs[i]*Ms[i]*ts[i])%N
E2 =iroot(sum,e)[0]
print(E2)
#E2=561236991551738188085

RSA 基本原理