sagemath

sagemath是免费的,开源的数学软件.

这篇笔记主要是学习风二西RSA中的sage脚本

Sage

定义

1
2
3
4
5
6
R.<X> = PolynomialRing(Zmod(n))
#Zmod(n):指定模，定义界限为n的环；Z表示整数；指定模是划定这个环的界限，就是有效的数字只有从0到n，其他的都通过与n取模来保证在0～n这个范围内；Zmod代表这是一个整数域中的n模环
#ZZ：整数环；QQ：有理数环；RR：实数环；CC：复数环
#R：只是一个指针，指向用polynomialring指定的那个环（可以使用任意字符）
#PolynomialRing：这个就是说建立多项式环
#.<X>：指定一个变量的意思（可以用任意字符）

P15-m高位泄露

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#sage
import libnum
n= 151960946972702081117093360145150451962009606399284283949493014851527184623949643832244795119390951664496262788801113061738745471705109651801469941245713981102683597278171804859002235073409069064532316371103411496330579589757997270705141792018944994603558174557515947534514865010671376327712345796006705526541
c= 175676150266417004297584173166433352018610464097263332979457040860199735122833311628588245224087655808166100611110577476473768211724924905653808872550861589950953763432355842437271483012029579464732704952936714503937167618229688691848715162564826927771471544937668578504504217271902336934966580193607269
e= 3
m1= 56006392793406045855300363310507945362344210576887867606743770445705804994335695867672312071808311296

def phase2(high_m, n, c,e):
    R.<x> = PolynomialRing(Zmod(n), implementation='NTL')
    m = high_m + x
    mm = m((m^e - c).small_roots()[0])
    print(libnum.n2s(int(mm)))

phase2(m1, n, c,e)

前半部分赋值不多讲了.

后半部分

def phase2(high_m, n, c,e):

定义函数phase2它有4个参数:high_m，n，c和e，分别表示高位消息，模数，加密的密文和私钥的一部分。

R.<x> = PolynomialRing(Zmod(n),

在函数中,NTL实现的PolynomialRing用于创建一个多项式环,并将其赋值给变量R.

NTL是一个高效的算法库，提供了许多用于处理数字和数学对象的函数和类。在这个函数中，NTL被用来实现多项式环的创建和操作。

m = high_m + x

在函数中，使用R.<x>创建了一个多项式环，其中x是多项式环中的变量。然后，将高位消息high_m与变量x相加，得到一个新的多项式m。这个新的多项式表示了高位消息和多项式环中的变量x的和。

mm = m((m^e - c).small_roots()[0])

使用small_roots[0]查找新多项式的所有小根,并将第一个小根赋给mm

这个步骤通常用于实现解密算法，其中使用私钥的一部分e将密文解密，并得到原始的高位消息。在密码学中，多项式的幂运算和小根查找通常用于解密操作，因为它们可以保持解密算法的解密强度，并且支持快速的解密计算。

总之，这段Python代码计算了一个新的多项式，用于实现密码学中的解密算法，并将解密后的高位消息存储在变量mm中。

P16-p高位攻击

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# sage
import libnum

p1= 551581766292640655058534159900370524723734298544296751888645281072588008930437002883229025
ct= 27616541175541912383218841794378477717815100351988988641692593787846567965685907
n= 4995188658553705943237642532637304629478558129154430053479887629657910186344578814092490939220270680936940085561619116103756070902375782856967186935569194381091567812272761869489784948925559108385286524919163973854841629509523338758606437479542140873137379396604477925588114110481990101764862712672385253154995559211448854670856757011948150593560101811692195031992591676518380681334005774239425210825578853564265774211044169731503039032800374149616144947247563714849211672844856816717791465223669720134064054505673626293544306335922034862053894152278185322272651233992668175851709547703618064746387826405747744796127
c= 2005089848291064787148397448696687012344549626289710371660666077296710969261963428559912230419177503733126688744998949915549792926349782034439468051424905955087887147908837962401856792709146385604115212224077711214152935860564769050302142687555048221193434813755593333341645718609796091120105920787139187265787211778283282773103775731410415083893525197003922165306656644599607471820759400664473582020509588222195178572645191458386808126222735109448423311957333471405829359240223280696911351515693567557505110795635614114177392022190068652386642392782128113497695555152751282349166919854788352365528525515800671319964
kbits = 724
def phase3(high_p, n):
    R. < x > = PolynomialRing(Zmod(n), implementation='NTL')
    p = high_p + x
    x0 = p.small_roots(X=2 ^ kbits, beta=0.1)[0]

    P = int(p(x0))
    Q = n // P
    assert n == P * Q
    return P, Q
p, q = phase3(p1, n)
print(p)
print(q)
phi = (p - 1) * (q - 1)
d = libnum.invmod(e, phi)
m = pow(c, d, n)
print(libnum.n2s(int(m)))

def phase3(high_p, n):

定义了一个函数,有两个参数

R. < x > = PolynomialRing(Zmod(n), implementation='NTL')

在函数中,NTL实现的PolynomialRing用于创建一个多项式环,并将其赋值给变量R.

p = high_p + x

将高位素数high_p与多项式环中的变量x相加，得到一个以x为未知数的多项式p。

x0 = p.small_roots(X=2 ^ kbits, beta=0.1)[0]

计算这一行多项式p的根.函数small_roots将返回一个包含多项式p的根的列表.后面的[0]获取列表的第一个元素,即最小的正整数根.

small_roots的两个参数是X和beta。X是一个正整数，定义了根的上限。在这里，我们使用2 ^ kbits来定义一个具有kbits位的上限。beta是一个小于1的正实数，用于确定多项式的下限。

综上所述，这个函数的目的是使用NTL库的多项式操作来计算合数n的因子之一。这是因数分解算法的第三阶段，通常称为光滑定位阶段。它包括寻找小于某个上限的光滑整数，其中光滑整数指的是一个质因子分解只包含小质数的整数

P = int(p(x0))

这一行计算多项式 p 在 x0 处的值，并将结果存储在变量 P 中。

前面计算出的 x0 是多项式 p 的一个根，将它代入多项式 p 中，可以得到一个整数值。由于我们使用的是模 n 下的多项式，所以使用 int() 函数将其转换为整数值。

剩下三行不做赘述

P17-d低位攻击

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import libnum

def getFullP(low_p, n):
    R. < x > = PolynomialRing(Zmod(n), implementation='NTL')
    p = x * 2 ^ bit + low_p
    root = (p - n).monic().small_roots(X=2 ^ 128, beta=0.4)
    if root:
        return p(root[0])
    return None

def phase4(low_d, n, c):
    maybe_p = []
    for k in range(1, 4):
        p = var('p')
        p0 = solve_mod([3 * p * low_d == p + k * (n * p - p ^ 2 - n + p)], 2 ^ bit)
        maybe_p += [int(x[0]) for x in p0]
    # print(maybe_p)
    for x in maybe_p:
        P = getFullP(x, n)
        if P: break

    P = int(P)
    Q = n // P

    assert P * Q == n
    print(P)
    print(Q)

    d = inverse_mod(3, (P - 1) * (Q - 1))
    print(d)
    print(libnum.n2s(int(power_mod(c, d, n))))

bit = 486
n = 99233273001596380809501393613886417854988989363311895592445631124571940638105064581031336422148895730117448547059137492090852484233539441265373247940823283633017582469362503632785297924194187912199716752955609363457416190782142095008241313065484612071705711161086869849047664563205898255359661312582650481473
e = 3
c = 175676150266403937224898870626869248307097859453341599800113943191154294552011908698393750389195590199207971365632903719917006078351629939912360175671032635640354766675409868021903917260597989036476083685690139071290022752606720020238530580507331902326179201548484337939338062870542095137303322195300197
d1 = 66155515334397587206334262409257611903325992908874597061630420749714627092070043054020890948099263820078299031372758328060568322822359627510248831960548842374360111368587702677016263988651746874367056185352095585037936034196599496577057035033718066207964292781685419156037246789689219471468151618592221802699

phase4(d1, n, c)

第一个函数getFullP

1
2
3
4
5
6
7
def getFullP(low_p, n):
    R. < x > = PolynomialRing(Zmod(n), implementation='NTL')
    p = x * 2 ^ bit + low_p
    root = (p - n).monic().small_roots(X=2 ^ 128, beta=0.4)
    if root:
        return p(root[0])
    return None

定义了一个函数getFullP,有两个参数,low_p和n.low_p是一个整数,表示大素数的后导部分,n是需要分解的合数.

p = x * 2 ^ bit + low_p

定义了一个一个以 x 为未知数的多项式p由 x * 2 ^ bit 加上常数low_p组成

monic() 方法可以将多项式的首项系数设为1，以避免系数带来的影响。

ai非说p-n等价于(p-n)/x不太理解

1
2
3
在代码中，`(p - n)` 是一个多项式，表示为 $p(x) - n$，其次数为 $m$，首项系数为 $1$，次高项系数为 $-n$。而 `(p - n)/x` 也是一个多项式，表示为 $(p(x) - n)/x$，其次数为 $m-1$，首项系数为 $1$，次高项系数为 $-n/x$。两个多项式只有系数项不同，而其次数均为 $m-1$。

在计算过程中，我们只需要考虑这个多项式在模 $2^{128}$ 意义下的小根。由于我们只需要这个多项式的首项系数为 $1$，因此无论是使用 `(p - n)` 还是 `(p - n)/x`，都可以得到相同的小根。因此，`(p - n)` 与 `(p - n)/x` 在计算 $p$ 在模 $2^{128}$ 意义下的小根时是等价的。

综上所述，这个函数的目的是计算大合数 n 的一个因子。

第二个函数phase4

1
2
3
4
5
6
7
8
9
10
def phase4(low_d, n, c):
    maybe_p = []
    for k in range(1, 4):
        p = var('p')
        p0 = solve_mod([3 * p * low_d == p + k * (n * p - p ^ 2 - n + p)], 2 ^ bit)
        maybe_p += [int(x[0]) for x in p0]
    # print(maybe_p)
    for x in maybe_p:
        P = getFullP(x, n)
        if P: break

p = var('p')

定义了一个名为p的符号变量,符号变量和Python中的变量不同，它不会自动赋值或改变，而是仅用于表示数学表达式中的符号。

例如，如果我们定义了符号变量x和y，那么我们可以通过x + y表示x和y的和，而不需要指定它们的值。在这个例子中，定义了一个名为p的符号变量，用于在后续的求解中引用。

1
就是说这样定义的x y可以在没有赋值的情况下使用

p0 = solve_mod([3 * p * low_d == p + k * (n * p - p ^ 2 - n + p)], 2 ^ bit)

这行代码使用了SageMath的solve_mod函数，它可以解决模方程。方程的左侧为$3 \cdot p \cdot low_d$，右侧为$p + k \cdot (n \cdot p - p ^ 2 - n + p)$，其中$k$是一个在1到3之间的整数。求解模$2^{bit}$意味着$p$的值将是一个$bit$位二进制数。p0将是所有解的列表，每个解都是一个元组，包含唯一的一个元素$p$的值。

solve_mod函数

SageMath是一款基于Python的数学计算软件，solve_mod()函数是SageMath中的一个模数方程求解函数，它可以求解形如f(x) = 0 (mod m)的模数方程。其中，f(x)是一个关于变量x的多项式，m是模数。该函数的返回值是所有满足方程的x值的列表。在此处，p0 = solve_mod([3 * p * low_d == p + k * (n * p - p ^ 2 - n + p)], 2 ^ bit)表示求解方程3plow_d = p + k*(n*p - p^2 - n + p) (mod 2^bit)，其中p是变量，low_d、n、k、bit都是已知数值。函数solve_mod()会返回所有满足方程的p值的列