ctf 密碼學常見算法總結

作者：0431實驗室
公眾號：吉林省信睿網絡

一、歐拉函數（phi）

函數內容

通式：

其中p1, p2……pn為x的所有質因數，x是不為0的整數。

φ(1)=1（和1互質的數(小于等于1)就是1本身）。

注意：每種質因數只一個。比如12=223那么φ（12）=φ（43）=φ（2^23^1）=（2^2-2^1）*（3^1-3^0）=4

若n是質數p的k次冪，

因為除了p的倍數外，其他數都跟n互質。

設n為正整數，以 φ(n)表示不超過n且與n互素的正整數的個數，稱為n的歐拉函數值

φ：N→N，n→φ(n)稱為歐拉函數。

歐拉函數是積性函數——若m,n互質，

如：φ(15)=φ(3)·φ(5)=2·4=8

特殊性質：當n為奇質數時，

證明與上述類似。

若n為質數則

函數表

0~100歐拉函數表（“x?”代表十位數，“x”代表個位數）

φ(100)=40

二、費馬小定理

版本一：

若a為一個整數，p為一個素數

那么a的p次方再減去a一定為p的倍數（同余）

記為

版本二：

把a提出來

當a不是p的倍數時，可以寫成（p必須為一個素數）

三、費馬歐拉定理

1736年歐拉證明費馬小定理是對的，給出更一般的定理：

若滿足a為一個整數，n為一個與a互素的整數，即a⊥n，那么

所以有了費馬歐拉定理（在數論中命名）

四、模反函數

如果兩個正整數e和n互質，那么一定可以找到整數d，使得 e * d - 1 被n整除，或者說e * d被n除的余數是1。這時，d就叫做e的“模反元素”。歐拉定理可以用來證明模反元素必然存在。兩個整數a,b，它們除以整數M所得的余數相等：a ≡ b(mod m)，比如說5除3余數為2，11除3余數也為2，于是可寫成11 ≡ 5(mod 3)。

五、歐幾里得算法（輾轉相除法-求最大公約數）

歐幾里得算法是求最大公約數的算法, 也就是輾轉相除法。記 gcd(a,b) 為a和b的最大公約數，歐幾里得算法的基本原理是gcd(a,b)==gcd(b,a%b),(b!=0) 和 gcd(a,0)==a 。

基本原理證明：

第一步：令c=gcd(a,b)，則設a=mc，b=nc

第二步：可知r =a-kb=mc-knc=(m-kn)c 【r=a%b】

第三步：根據第二步結果可知c也是r的因數

第四步：可以斷定m-kn與n互素【否則，可設m-kn=xd,n=yd,(d>1)，則m=kn+xd=kyd+xd=(ky+x)d，則a=mc=(ky+x)dc，b=nc=ycd，故a與b最大公約數≥cd，而非c，與前面結論矛盾】

從而可知gcd(b,r)=c，繼而gcd(a,b)=gcd(b,r)，得證

擴展歐幾里得算法

擴展歐幾里得算法基于歐幾里得算法，能夠求出使得 ax+by=gcd(a,b) 的一組x,y。

對照下圖更容易理解

同樣按照歐幾里得算法的遞歸過程一樣，到邊界的時候b=0，這時候整數解非常好找，就是x=1，y=0。

六、RSA

①找兩素數p和q，取n=p*q （N）

②r=φ(n)=φ(p)φ(q)=(p-1)(q-1)

③e∈Z，e＜r 且 e⊥r (必須)

。。。。。。公鑰（N，e）

④d（模逆元），滿足ed-1=r的倍數

d*e%r=1

求d令ed ≡ 1 (mod r)

。。。。。。私鑰（N，d）

加密：

Bob用公鑰加密給Alice傳數 Bob 傳 m 給 Alice，要求m＜N

Alice得到密文c

解密：

Alice用私鑰破解密文得到明文

？即是明文m

解釋：

差個正負號，但是都是N的倍數，都成立

兩邊同時做d次方

最后一步根據費馬歐拉定理得來

所以得到解密式子：

對明文m進行加密：c = pow(m, e, N),可以得到密文c。

對密文c進行解密：m = pow(c, d, N),可以得到明文m。

pow(x, y, z)：效果等效pow(x, y)1% z， 先計算x的y次方，如果存在另一個參數z，需要再對結果進行取模。即pow(x,y,z)=x^y(mod z)

七、實例-共模攻擊

所謂共模攻擊，是指多個用戶共用一個模數n，各自有自己的e和d，在幾個用戶之間共用n會使攻擊者能夠不用分解n而恢復明文。 例如假設m為信息明文，兩個加密密鑰為e1和e2，公共模數為n，則：

c1 = pow(m, e1, n) – c1 = m^e1%n
c2 = pow(m, e2, n) – c2 = m^e2%n

分別拿對應的私鑰來加密，可以得到相同的明文m

m = pow(c1, d1, n) – m = c1^d1%n
m = pow(c2, d2, n) – m = c2^d2%n

假設攻擊者已知n,e1,e2,c1,c2，即可得到明文p，因為e1和e2互質，所以使用歐幾里得算法可以找到能夠滿足以下條件的x，y：

pow(x,e1)+pow(y,e2)=1 – x^e1+y^e2=1（式中，x、y皆為整數，但是一正一負）

因為：c1 = m^e1%n ；c2 = m^e2%n

所以：(c1^xc2^y)%n = ((m^e1%n)^x(m^e2%n)^y)%n

根據模運算性質，可以化簡為：(c1^xc2^y)%n = ((m^e1)^x(m^e2)^y)%n

即：(c1^x*c2^y)%n = (m^(e1x+e2y))%n

有前面提到：e1x+e2y = 1

所以 (c1^xc2^y)%n = (m^(1))%n (c1^xc2^y)%n = m%n

即 c1^x*c2^y ≡ m （mod n）

假設x為負數，需再使用歐幾里得算法來計算pow(c1,-1)，則可以得到

pow(pow(c1,-1),-x) * pow(c2,y) = m mod(n) – {[c1^(-1)]^(-x)}*(c2^y) = m mod n

m = c1^x*c2^y mod N

在數論模運算中，要求一個數的負數次冪，與常規方法并不一樣。

比如此處要求c1的x次冪，就要先計算c1的模反元素c1r，然后求c1r的-x次冪

如果m＜n，則m可以被計算出來。

例題：

某次ctf比賽中的題

共模攻擊的腳本+測試代碼

題中給了n,e1,e2,c1,c2

運行腳本解出10進制的m，轉換成hex，再轉換成字符串即可得到flag。

總的腳本如下：

# -*- coding:utf-8 -*-
from gmpy2 import invert
def gongmogongji(n, c1, c2, e1, e2):
    def egcd(a, b):
        if b == 0:
            return a, 0
        else:
            x, y = egcd(b, a % b)
            return y, x - (a // b) * y
    s = egcd(e1, e2)
    s1 = s[0]
    s2 = s[1]

    # 求模反元素
    if s1 < 0:
        s1 = - s1
        c1 = invert(c1, n)
    elif s2 < 0:
        s2 = - s2
        c2 = invert(c2, n)
    m = pow(c1, s1, n) * pow(c2, s2, n) % n
    return m

n= 103109065902334620226101162008793963504256027939117020091876799039690801944735604259018655534860183205031069083254290258577291605287053538752280231959857465853228851714786887294961873006234153079187216285516823832102424110934062954272346111907571393964363630079343598511602013316604641904852018969178919051627
e1= 13
e2= 15
c1= 13981765388145083997703333682243956434148306954774120760845671024723583618341148528952063316653588928138430524040717841543528568326674293677228449651281422762216853098529425814740156575513620513245005576508982103360592761380293006244528169193632346512170599896471850340765607466109228426538780591853882736654
c2= 79459949016924442856959059325390894723232586275925931898929445938338123216278271333902062872565058205136627757713051954083968874644581902371182266588247653857616029881453100387797111559677392017415298580136496204898016797180386402171968931958365160589774450964944023720256848731202333789801071962338635072065

result = gongmogongji(n, c1, c2, e1, e2)
print result
m1=hex(50937517501984079318479184180525081694999782691988219077509947184814275476037417455150384)
print m1
import binascii
m2=binascii.unhexlify(b'666c61672d3534643364623563316566636437616661353739633337626362353630616530')
print m2

最后得到flag：

flag-54d3db5c1efcd7afa579c37bcb560ae0

參考文獻

https://blog.csdn.net/qq_23077403/article/details/86099229 https://blog.csdn.net/qq_23077403/article/details/86099229

本文由 Seebug Paper 發布，如需轉載請注明來源。本文地址：http://www.bjnorthway.com/1055/