RSA Notes 4

Notes
CTFSeason2
发布日期:   2021-01-22

huangx607087学习RSA的笔记4

0.简介：

一个密码学废物的学习笔记，很菜，别看，以后会不定期更新

An Overview of some special kinds of RSA and their solutions.

一个对过去RSA学习的回顾及其实战中题目的应对方法，很多方法在以前的笔记（RSA Notes 1 & RSA in GF）中提及过，不过这次是结合了例题来讲解的，很多地方还是直接用的脚本，因为我太fw了

1. Overview of RSA in GF

RSA在GF域上的多项式的表现形式，根据之前笔记中的内容，这种题目就是利用Sagemath把RSA中的模多项式分解成两个本原多项式，然后注意到这两个本源多项式$P,Q$的$\phi$值为$p^e-1$，其中$p$是GF域中的素因数，$e$为指数，分别取决于$P$的次数和$Q$的次数，因为所有的$p^e-1$个多项式都无法与本源多项式$P$互约。

所以我们可以先来看看这样一道题目：

1
2
3
Prime: 43753
Modulus: 34036*y^177 + 23068*y^176 + 13147*y^175 + 36344*y^174 + 10045*y^173 + 41049*y^172 + 17786*y^171 + 16601*y^170 + 7929*y^169 + 37570*y^168 + 990*y^167 + 9622*y^166 + 39273*y^165 + 35284*y^164 + 15632*y^163 + 18850*y^162 + 8800*y^161 + 33148*y^160 + 12147*y^159 + 40487*y^158 + 6407*y^157 + 34111*y^156 + 8446*y^155 + 21908*y^154 + 16812*y^153 + 40624*y^152 + 43506*y^151 + 39116*y^150 + 33011*y^149 + 23914*y^148 + 2210*y^147 + 23196*y^146 + 43359*y^145 + 34455*y^144 + 17684*y^143 + 25262*y^142 + 982*y^141 + 24015*y^140 + 27968*y^139 + 37463*y^138 + 10667*y^137 + 39519*y^136 + 31176*y^135 + 27520*y^134 + 32118*y^133 + 8333*y^132 + 38945*y^131 + 34713*y^130 + 1107*y^129 + 43604*y^128 + 4433*y^127 + 18110*y^126 + 17658*y^125 + 32354*y^124 + 3219*y^123 + 40238*y^122 + 10439*y^121 + 3669*y^120 + 8713*y^119 + 21027*y^118 + 29480*y^117 + 5477*y^116 + 24332*y^115 + 43480*y^114 + 33406*y^113 + 43121*y^112 + 1114*y^111 + 17198*y^110 + 22829*y^109 + 24424*y^108 + 16523*y^107 + 20424*y^106 + 36206*y^105 + 41849*y^104 + 3584*y^103 + 26500*y^102 + 31897*y^101 + 34640*y^100 + 27449*y^99 + 30962*y^98 + 41434*y^97 + 22125*y^96 + 24314*y^95 + 3944*y^94 + 18400*y^93 + 38476*y^92 + 28904*y^91 + 27936*y^90 + 41867*y^89 + 25573*y^88 + 25659*y^87 + 33443*y^86 + 18435*y^85 + 5934*y^84 + 38030*y^83 + 17563*y^82 + 24086*y^81 + 36782*y^80 + 20922*y^79 + 38933*y^78 + 23448*y^77 + 10599*y^76 + 7156*y^75 + 29044*y^74 + 23605*y^73 + 7657*y^72 + 28200*y^71 + 2431*y^70 + 3860*y^69 + 23259*y^68 + 14590*y^67 + 33631*y^66 + 15673*y^65 + 36049*y^64 + 29728*y^63 + 22413*y^62 + 18602*y^61 + 18557*y^60 + 23505*y^59 + 17642*y^58 + 12595*y^57 + 17255*y^56 + 15316*y^55 + 8948*y^54 + 38*y^53 + 40329*y^52 + 9823*y^51 + 5798*y^50 + 6379*y^49 + 8662*y^48 + 34640*y^47 + 38321*y^46 + 18760*y^45 + 13135*y^44 + 15926*y^43 + 34952*y^42 + 28940*y^41 + 13558*y^40 + 42579*y^39 + 38015*y^38 + 33788*y^37 + 12381*y^36 + 195*y^35 + 13709*y^34 + 31500*y^33 + 32994*y^32 + 30486*y^31 + 40414*y^30 + 2578*y^29 + 30525*y^28 + 43067*y^27 + 6195*y^26 + 36288*y^25 + 23236*y^24 + 21493*y^23 + 15808*y^22 + 34500*y^21 + 6390*y^20 + 42994*y^19 + 42151*y^18 + 19248*y^17 + 19291*y^16 + 8124*y^15 + 40161*y^14 + 24726*y^13 + 31874*y^12 + 30272*y^11 + 30761*y^10 + 2296*y^9 + 11017*y^8 + 16559*y^7 + 28949*y^6 + 40499*y^5 + 22377*y^4 + 33628*y^3 + 30598*y^2 + 4386*y + 23814
Ciphertext: 5209*x^176 + 10881*x^175 + 31096*x^174 + 23354*x^173 + 28337*x^172 + 15982*x^171 + 13515*x^170 + 21641*x^169 + 10254*x^168 + 34588*x^167 + 27434*x^166 + 29552*x^165 + 7105*x^164 + 22604*x^163 + 41253*x^162 + 42675*x^161 + 21153*x^160 + 32838*x^159 + 34391*x^158 + 832*x^157 + 720*x^156 + 22883*x^155 + 19236*x^154 + 33772*x^153 + 5020*x^152 + 17943*x^151 + 26967*x^150 + 30847*x^149 + 10306*x^148 + 33966*x^147 + 43255*x^146 + 20342*x^145 + 4474*x^144 + 3490*x^143 + 38033*x^142 + 11224*x^141 + 30565*x^140 + 31967*x^139 + 32382*x^138 + 9759*x^137 + 1030*x^136 + 32122*x^135 + 42614*x^134 + 14280*x^133 + 16533*x^132 + 32676*x^131 + 43070*x^130 + 36009*x^129 + 28497*x^128 + 2940*x^127 + 9747*x^126 + 22758*x^125 + 16615*x^124 + 14086*x^123 + 13038*x^122 + 39603*x^121 + 36260*x^120 + 32502*x^119 + 17619*x^118 + 17700*x^117 + 15083*x^116 + 11311*x^115 + 36496*x^114 + 1300*x^113 + 13601*x^112 + 43425*x^111 + 10376*x^110 + 11551*x^109 + 13684*x^108 + 14955*x^107 + 6661*x^106 + 12674*x^105 + 21534*x^104 + 32132*x^103 + 34135*x^102 + 43684*x^101 + 837*x^100 + 29311*x^99 + 4849*x^98 + 26632*x^97 + 26662*x^96 + 10159*x^95 + 32657*x^94 + 12149*x^93 + 17858*x^92 + 35805*x^91 + 19391*x^90 + 30884*x^89 + 42039*x^88 + 17292*x^87 + 4694*x^86 + 1497*x^85 + 1744*x^84 + 31071*x^83 + 26246*x^82 + 24402*x^81 + 22068*x^80 + 39263*x^79 + 23703*x^78 + 21484*x^77 + 12241*x^76 + 28821*x^75 + 32886*x^74 + 43075*x^73 + 35741*x^72 + 19936*x^71 + 37219*x^70 + 33411*x^69 + 8301*x^68 + 12949*x^67 + 28611*x^66 + 42654*x^65 + 6910*x^64 + 18523*x^63 + 31144*x^62 + 21398*x^61 + 36298*x^60 + 27158*x^59 + 918*x^58 + 38601*x^57 + 4269*x^56 + 5699*x^55 + 36444*x^54 + 34791*x^53 + 37978*x^52 + 32481*x^51 + 8039*x^50 + 11012*x^49 + 11454*x^48 + 30450*x^47 + 1381*x^46 + 32403*x^45 + 8202*x^44 + 8404*x^43 + 37648*x^42 + 43696*x^41 + 34237*x^40 + 36490*x^39 + 41423*x^38 + 35792*x^37 + 36950*x^36 + 31086*x^35 + 38970*x^34 + 12439*x^33 + 7963*x^32 + 16150*x^31 + 11382*x^30 + 3038*x^29 + 20157*x^28 + 23531*x^27 + 32866*x^26 + 5428*x^25 + 21132*x^24 + 13443*x^23 + 28909*x^22 + 42716*x^21 + 6567*x^20 + 24744*x^19 + 8727*x^18 + 14895*x^17 + 28172*x^16 + 30903*x^15 + 26608*x^14 + 27314*x^13 + 42224*x^12 + 42551*x^11 + 37726*x^10 + 11203*x^9 + 36816*x^8 + 5537*x^7 + 20301*x^6 + 17591*x^5 + 41279*x^4 + 7999*x^3 + 33753*x^2 + 34551*x + 9659

这道题给出了一个$p=43753$，和两个多项式$n,c$，很显然，根据以往的传统，我们把$n$放到sagemath中进行分解。

1-1

不过我们发现他最后竟然带了个系数$34036$，计算了一下$\phi(34036)=16632$，所以最后的$\phi(n)=16632(43753^{65})(43753^{112})$，然后就是求逆元。不过最后发现这个$16632$乘不乘最后的结果都一样，不知道是为什么。

然后就是常规操作了，我们根据RSA的常规解密，就可以解出$m$。这里到最后应该是把$m$多项式的次数从低到高的系数拿出来转换成字符（而不是视为$43753$进制最后转换成$10$进制后long_to_bytes）,最后的答案就很简单了

1-2

2.Overview of Coppersmith

以下部分位Coppersmith相关例题讲解

PART 1

1
2
3
4
n=0x67de16e8ceaece4a123ad278b249a9acde81174d4287889d68dbb7939fdfa28f3a927c4e1c71f9b7b036c7ce287806105954fb9086bfe3dbe5f82d156f4151c9fe74e32f6ce8bb239c2d55cb6628e53941628ccbd294aa101687160b578decf716f348ea42922358946e7706daf044be08a9bcd8ea248b597eeb3a1e16781247dec66a0976046de5b2603315ab5dc17120a558db56213e66989c0895492151fb5a0784fa346dfeebf2b1f71b3c7dbf135abfd4499d4f83b6d0b4c68fe5b1fe14e383d4c7cc78065cfed1831bd2e19c06b270e4ebfb9d09f3431d613301106c7762dace771e730c3268ad549e20202ac1f77d47eb18f82693e6e974f783a88793
e=3
c=0x54d055d31d0186b4914292a281ce71ecd9e5f2a441e68180ab0d6bb3e08412254d3465b44d1aa49d5c1926f3d72507bb7f89c5614a190957c4c22da4e966ecf632c914c5cce942bd4ee916c3d28ab27863e1ec9a1058fbc10b3bf672765e51428cd8022a7985d01570a72091694d0c91a205319316dd5c1eaa8f6486673512940e19a65
(m>>72)<<72=0x464c41477b325e38727361373538393639336663363839633737633566353236326436000000000000000000

这道题给出了$n,e,c$，同时还有一个$512$位长的$m$，不过最低的$72$位被省略了，所以现在我们就使用我在RSA Notes 1中第0x08部分发布的脚本，补充完整参数，放入sagemath-notebook中运行即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
n = #你已知的n值
e = 3
m = randrange(n)#不要改
c = pow(m, e, n)#不要改
beta = 1
epsilon = beta^2/7#不要改
nbits = n.nbits()#不要改
kbits=#m被掩盖的字位数
print(nbits,kbits)
mbar = #你得到的不完整的m值
c = #你得到的c值
print ("upper %d bits (of %d bits) is given" % (nbits-kbits, nbits))
PR.<x> = PolynomialRing(Zmod(n))
f = (mbar + x)^e - c
print (m)
x0 = f.small_roots(X=2^kbits, beta=1)[0]  # find root < 2^kbits with factor = n1
print( mbar + x0)

PART 2

1
2
3
4
n=0x6546140f6d20fb1af8755ba3925274f8df3f175ea783e3f23748429fe6602477239b51e5c20b201b82e210402ebbfc159cb548117a4c2e1b73bbee26bbc04f5388ed3710beb66db0e1b6253030944c791529bc6cf4959851fde47602dcc116468038f852b766d418a7b2d4b83edef71e82b6465a3726d2f9d228dc0a99c01f277e28176c93d7059b3ad0b20f33b6b26785a22a3e867c11a9dc564311cc4cd6b7a3f605c9e7c7e44896181713269faf5600e98cb12450316bad55cda3e1ed24bbdac22cf4c8d23f1f4767336aebea9c638d6258f80c858e5b01be39edf7eb245c3c4639ef6de9edaf904808e09e141030ec503260418b23a0347bf224e65766f3
e=65537
c=0x4f92bcf8674e17ac7901a68b125bea2b7c2e5e5b7da9d23b90db42fb8e7ae60580b6055310d1a71daa8787c3a386914212e55e89f26155228e243efb444791469f8decc7cb6663d84a8ad404ae3b0bf07e3777a90db767c1ea433cbb8cc276a01025e1ffa8f1ba92b9f90f9b2822a1789b6953ba3a1f9c948a8fc834b9873a8a0ad1c58c34ddc53a2551d85f54166b205ce53c2f883ba59fe4bd181b1bc9a9b7d9d3d9204c0310d20c14804dc7d7d8a241d360216eff12b55c87f9dbddcab23855f75c6105e0de4f44944317b04dbb89cb9bb2f381c375b0e166cf5f547967e07ab1a86287dae6e555905b8069846474169cef605af66be22ec884d3718997a
(p>>128)<<128=0x8ae08a8ccda172cc5768c98c935b06a185a5f86f1020ce864929dd61d0d6511141e94f589b4c10754fe4b278207414caedc5a0c47ca091ef3dad80c15b05776d4c574759b50106585973e7f7cda6d01db4bcfbb671151069287f276bb6c18d04cab2dfccf70a72a5edbc23fd636da98900000000000000000000000000000000

这道题给出了$p$的值，不过$p$缺失了最后的$128$位，所以我们可以补全以下脚本，然后放入sagemath中运行即可获得完整的$p$值，进而分解$n$，常规解密即可。

1
2
3
4
5
6
7
8
9
10
11
n = #填写n值
p_fake = #填写p值
pbits = p_fake.nbits()
kbits = #填写p失去的低位位数
pbar = p_fake & (2^pbits-2^kbits)
print ("upper %d bits (of %d bits) is given" % (pbits-kbits, pbits))
PR.<x> = PolynomialRing(Zmod(n))
f = x + pbar
x0 = f.small_roots(X=2^kbits, beta=0.4)[0]  # find root < 2^kbits with factor >= n^0.3
p= x0 + pbar
print (hex(p))

PART 3

1
2
3
4
n=0x8449fe9c8f1ddf7b08b53af7e3f55f9199fdc07b05ae7bda1737159ee985c8ea7d46dd1ac82cf23fef91b119822667d4fe7d98a2a46d1fc38f9dc05e9fb8e6ea07087f77d8dbda45877eb5babb7bc58af8caccdcbe89cf0cb994ce51fa5d45565fbc1b1797984663bb912ce2c9391ba6b76c92c4ac2e6b5d9c1242fdc75f36f7
e=3
c=0x4ffb1114e37dd59103dae4c48581bb592e1bc0a2ec94f10f9f391084267aad0715a09776e074464d9581e00ad0af4f4e7ec2adc0d4455c7c23b52f76d1ea3801ced06c6db167614aae99a2ad44e1c00ac3eb043405e2f80c7c2c99e72fea9bfe708972f8eb1e419cb60b724bac9b2139283d6a1c34c137c312e20c12433978d2
d%(2**512)=0xf0a11feccbadcce7330f2d3b65bac041514c5b4cec2c7260923df431b60806de728822d256becee44d84d8ff4c4f3b95b5c2a4707ced42e0184e46cc043971b

这次，我们已知的是$n,e,c$同时还给出了$d$的最低$512$位，我们也可以直接补全以下脚本，然后放入sagemath中即可获得完整的$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
def partial_p(p0, kbits, n):
    PR.<x> = PolynomialRing(Zmod(n))
    nbits = n.nbits()
    f = 2^kbits*x + p0
    f = f.monic()
    roots = f.small_roots(X=2^(nbits//2-kbits), beta=0.3)  # find root < 2^(nbits//2-kbits) with factor >= n^0.3
    if roots:
        x0 = roots[0]
        p = gcd(2^kbits*x0 + p0, n)
        return ZZ(p)
def find_p(d0, kbits, e, n):
    X = var('X')
    for k in range(1, e+1):
        results = solve_mod([e*d0*X - k*X*(n-X+1) + k*n == X], 2^kbits)
        for x in results:
            p0 = ZZ(x[0])
            p = partial_p(p0, kbits, n)
            if p:
                return p
if __name__ == '__main__':
    n = #填写n值
    e = 3
    d = #填写不完整的d值
    print(hex(d))
    beta = 0.5
    epsilon = beta^2/7
    nbits = n.nbits()
    print ("nbits:%d:"%(nbits))
    kbits = #填写已知d的低位的二进制位数
    print ("kbits:%d"%(kbits))
    d0 = d & (2^kbits-1)
    print ("lower %d bits (of %d bits) is given" % (kbits, nbits))
    p = find_p(d0, kbits, e, n)
    print ("found p: %d" % p)
    q = n//p
    print (hex(d))
    dtrue=inverse_mod(e, (p-1)*(q-1))
    print(hex(dtrue))

PART 4

1
2
3
4
5
6
7
e=3
n1=78642188663937191491235684351005990853149481644703243255021321296087539054265733392095095639539412823093600710316645130404423641473150336492175402885270861906530337207734106926328737198871118125840680572148601743121884788919989184318198417654263598170932154428514561079675550090698019678767738203477097731989
c1=23419685303892339080979695469481275906709035609088426118328601771163101123641599051556995351678670765521269546319724616458499631461037359417701720430452076029312714313804716888119910334476982840024696320503747736428099717113471541651211596481005191146454458591558743268791485623924245960696651150688621664860
n2=98174485544103863705821086588292917749386955237408645745685476234349659452606822650329076955303471252833860010724515777826660887118742978051231030080666542833950748806944312437614585352818344599399156268450521239843157288915059003487783576003027303399985723834248634230998110618288843582573006048070816520647
c2=72080679612442543693944655041130370753964497034378634203383617624269927191363529233872659451561571441107920350406295389613006330637565645758727103723546610079332161151567096389071050158035757745766399510575237344950873632114050632573903701015749830874081198250578516967517980592506626547273178363503100507676
n3=91638855323231795590642755267985988356764327384001022396221901964430032527111968159623063760057482761918901490239790230176524505469897183382928646349163030620342744192731246392941227433195249399795012672172947919435254998997253131826888070173526892674308708289629739522194864912899817994807268945141349669311
c3=22149989692509889061584875630258740744292355239822482581889060656197919681655781672277545701325284646570773490123892626601106871432216449814891757715588851851459306683123591338089745675044763551335899599807235257516935037356212345033087798267959242561085752109746935300735969972249665700075907145744305255616

低指数广播攻击就是已知同一个明文$m$被多个不同的密钥加密后的结果，这个时候可以直接使用中国剩余定理解决，最后对结果开三次根号即位明文的值。

CRT的脚本有很多，比如说我博客中的0xGame Div 2中就有现成的脚本可以直接拿过来用，此处节省版面，不上脚本，因为更重要的内容在后面

PART 5

ORG 2021.1.22

1
2
3
4
n=0xa1c7556e895f8268b7a81c5cae3d1377f245ceb84b86878982c9869ed9a00fd1ec11a462831b812d7f973a385a1cdae9465c78085ef1d28fa52d8b151609c737e788c3ae9848c39cc2d62c8c73b7659d19e49301171e5df0d9eb6bd0ea0c0f2d64235372c04f88e6402f202783432d2a3cca4d7290e59e41afbe1c206495134d
e=7
c=0xa0e8306ed676f8f362c78feb0f3adfbaa068f28863941777bd07a7f41f4288220efe34227d1cba72597582f5c1d372394edfd3bd1c29686f30ab9c84ab6bcbbb08920cfca210ecdf3bfac94f844b877a2b74bfeeafd47784978723e6ac78796c24022aa142f4a5715efde7be7e34a75665e6d984fea74e77d063d7e75d0b888c
x=0xa0e8306ed676f8f362c78feb0f3adfbaa068f28863941777bd07a7f41f4288220efe34227d1cba72935ee2338135a8152e68165e0f7adf45a898d6b32ea2fc8789f783a7af0ade6acd505e1c791058bb872d589f848e6bb5aa4eeceed04e62ff98b75d6cecd57f0b510486f3f18e9e2f3b7ec14a5ba6621d76161c54f9a5561f

其中$x$是对$m+1$加密的结果，也就是$(m+1)^7 \mod n$

这里就涉及到了相关明文攻击：

UPD 2021.2.18

UPD内容：删除了原版中错误的脚本代码，上了一个准确的代码

所谓RSA相关明文攻击，就是在已知$c\equiv m^e \pmod p$的情况下，同时还知道了$x\equiv (m+1)^e \pmod p$的情况，这个时候启动相关明文攻击，具体内容将在后面一篇RSA笔记中提到。

下面先上一下解密脚本，这里是知道了$x$和$x+b$的情形。当然，如果一次项不同，举个例子。比如我们知道的是$c=E(2m+3)$和$x=E(5m+8)$。可以得到$C=5^ec,X=2^ex$，那么我们就获得了$C=E(10m+15),X=E(10m+16)$的情形，填写$b=1,c=C,x=X$，那么我们就可以获得$10m \mod n$的计算结果，简单处理一下就可以获得$m$了。（CTF不是ACM，因此我们不需要把所有的步骤全放在一个文件里面，自己多数都是分部计算的，故关于如何凑m前面的系数，请自己根据提示构造）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#sagemath code
def attack(c1, c2, b, e, n):
    PR.<x>=PolynomialRing(Zmod(n))
    g1 = x^e - c1
    g2 = (x+b)^e - c2

    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic()
    return -gcd(g1, g2)[0]
n=#填写n值
c=#填写明文加密内容
x=#填写相关明文加密内容
e=#填写加密指数，不宜太大，一般不超过100
b=#填写一次函数相差的常数项
m = attack(c,x,b,e,n)
print(m)
#这是已知m和m+b的情形。如果知道了Am+B,Cm+D，可以将m前面的系数统一成GCD(A,C)后再求解。

PART 6

1
2
3
4
5
n=0xbadd260d14ea665b62e7d2e634f20a6382ac369cd44017305b69cf3a2694667ee651acded7085e0757d169b090f29f3f86fec255746674ffa8a6a3e1c9e1861003eb39f82cf74d84cc18e345f60865f998b33fc182a1a4ffa71f5ae48a1b5cb4c5f154b0997dc9b001e441815ce59c6c825f064fdca678858758dc2cebbc4d27
d=random.getrandbits(1024*0.270)
e=invmod(d,phin)
hex(e)=0x11722b54dd6f3ad9ce81da6f6ecb0acaf2cbc3885841d08b32abc0672d1a7293f9856db8f9407dc05f6f373a2d9246752a7cc7b1b6923f1827adfaeefc811e6e5989cce9f00897cfc1fc57987cce4862b5343bc8e91ddf2bd9e23aea9316a69f28f407cfe324d546a7dde13eb0bd052f694aefe8ec0f5298800277dbab4a33bb
c=pow(m,e,n)=0xe3505f41ec936cf6bd8ae344bfec85746dc7d87a5943b3a7136482dd7b980f68f52c887585d1c7ca099310c4da2f70d4d5345d3641428797030177da6cc0d41e7b28d0abce694157c611697df8d0add3d900c00f778ac3428f341f47ecc4d868c6c5de0724b0c3403296d84f26736aa66f7905d498fa1862ca59e97f8f866c

很显然，看到$e$这么大，并且$\ln d =0.27 \ln n< 0.292 \ln n$,很容易想到WinerAttack

不过试了好几个weinerattack的脚本都爆破失败，原因可能是因为此处的$\dfrac{\ln d}{\ln n}=0.27$，过于接近$0.292$了，导致了爆破的失败。

网上找到了一个与Winerattack相类似但不是Winerattack的脚本，填参后放入sagemath里用即可。

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
import time
debug = True
strict = False
helpful_only = True
dimension_min = 7 
def helpful_vectors(BB, modulus):
    nothelpful = 0
    for ii in range(BB.dimensions()[0]):
        if BB[ii,ii] >= modulus:
            nothelpful += 1
    print( nothelpful, "/", BB.dimensions()[0], " vectors are not helpful")
def matrix_overview(BB, bound):
    for ii in range(BB.dimensions()[0]):
        a = ('%02d ' % ii)
        for jj in range(BB.dimensions()[1]):
            a += '0' if BB[ii,jj] == 0 else 'X'
            if BB.dimensions()[0] < 60:
                a += ' '
        if BB[ii, ii] >= bound:
            a += '~'
        print( a)
def remove_unhelpful(BB, monomials, bound, current):
    if current == -1 or BB.dimensions()[0] <= dimension_min:
        return BB
    for ii in range(current, -1, -1):
        # if it is unhelpful:
        if BB[ii, ii] >= bound:
            affected_vectors = 0
            affected_vector_index = 0
            for jj in range(ii + 1, BB.dimensions()[0]):
                if BB[jj, ii] != 0:
                    affected_vectors += 1
                    affected_vector_index = jj
            if affected_vectors == 0:
                print( "* removing unhelpful vector", ii)
                BB = BB.delete_columns([ii])
                BB = BB.delete_rows([ii])
                monomials.pop(ii)
                BB = remove_unhelpful(BB, monomials, bound, ii-1)
                return BB
            elif affected_vectors == 1:
                affected_deeper = True
                for kk in range(affected_vector_index + 1, BB.dimensions()[0]):
                    if BB[kk, affected_vector_index] != 0:
                        affected_deeper = False
                if affected_deeper and abs(bound - BB[affected_vector_index, affected_vector_index]) < abs(bound - BB[ii, ii]):
                    print( "* removing unhelpful vectors", ii, "and", affected_vector_index)
                    BB = BB.delete_columns([affected_vector_index, ii])
                    BB = BB.delete_rows([affected_vector_index, ii])
                    monomials.pop(affected_vector_index)
                    monomials.pop(ii)
                    BB = remove_unhelpful(BB, monomials, bound, ii-1)
                    return BB
    return BB
def boneh_durfee(pol, modulus, mm, tt, XX, YY):
    # substitution (Herrman and May)
    PR.<u, x, y> = PolynomialRing(ZZ)
    Q = PR.quotient(x*y + 1 - u) # u = xy + 1
    polZ = Q(pol).lift()

    UU = XX*YY + 1

    # x-shifts
    gg = []
    for kk in range(mm + 1):
        for ii in range(mm - kk + 1):
            xshift = x^ii * modulus^(mm - kk) * polZ(u, x, y)^kk
            gg.append(xshift)
    gg.sort()

    # x-shifts list of monomials
    monomials = []
    for polynomial in gg:
        for monomial in polynomial.monomials():
            if monomial not in monomials:
                monomials.append(monomial)
    monomials.sort()
    
    # y-shifts (selected by Herrman and May)
    for jj in range(1, tt + 1):
        for kk in range(floor(mm/tt) * jj, mm + 1):
            yshift = y^jj * polZ(u, x, y)^kk * modulus^(mm - kk)
            yshift = Q(yshift).lift()
            gg.append(yshift) # substitution
    
    # y-shifts list of monomials
    for jj in range(1, tt + 1):
        for kk in range(floor(mm/tt) * jj, mm + 1):
            monomials.append(u^kk * y^jj)

    # construct lattice B
    nn = len(monomials)
    BB = Matrix(ZZ, nn)
    for ii in range(nn):
        BB[ii, 0] = gg[ii](0, 0, 0)
        for jj in range(1, ii + 1):
            if monomials[jj] in gg[ii].monomials():
                BB[ii, jj] = gg[ii].monomial_coefficient(monomials[jj]) * monomials[jj](UU,XX,YY)
    if helpful_only:
        BB = remove_unhelpful(BB, monomials, modulus^mm, nn-1)
        nn = BB.dimensions()[0]
        if nn == 0:
            print( "failure")
            return 0,0
    if debug:
        helpful_vectors(BB, modulus^mm)
    det = BB.det()
    bound = modulus^(mm*nn)
    if det >= bound:
        print( "We do not have det < bound. Solutions might not be found.")
        print( "Try with highers m and t.")
        if debug:
            diff = (log(det) - log(bound)) / log(2)
            print( "size det(L) - size e^(m*n) = ", floor(diff))
        if strict:
            return -1, -1
    else:
        print( "det(L) < e^(m*n) (good! If a solution exists < N^delta, it will be found)")
    if debug:
        matrix_overview(BB, modulus^mm)
    if debug:
        print( "optimizing basis of the lattice via LLL, this can take a long time")
    BB = BB.LLL()
    if debug:
        print( "LLL is done!")
    if debug:
        print( "looking for independent vectors in the lattice")
    found_polynomials = False
    
    for pol1_idx in range(nn - 1):
        for pol2_idx in range(pol1_idx + 1, nn):
            PR.<w,z> = PolynomialRing(ZZ)
            pol1 = pol2 = 0
            for jj in range(nn):
                pol1 += monomials[jj](w*z+1,w,z) * BB[pol1_idx, jj] / monomials[jj](UU,XX,YY)
                pol2 += monomials[jj](w*z+1,w,z) * BB[pol2_idx, jj] / monomials[jj](UU,XX,YY)
            PR.<q> = PolynomialRing(ZZ)
            rr = pol1.resultant(pol2)
            if rr.is_zero() or rr.monomials() == [1]:
                continue
            else:
                print( "found them, using vectors", pol1_idx, "and", pol2_idx)
                found_polynomials = True
                break
        if found_polynomials:
            break
    if not found_polynomials:
        print( "no independant vectors could be found. This should very rarely happen...")
        return 0, 0
    rr = rr(q, q)
    soly = rr.roots()
    if len(soly) == 0:
        print( "Your prediction (delta) is too small")
        return 0, 0
    soly = soly[0][0]
    ss = pol1(q, soly)
    solx = ss.roots()[0][0]
    return solx, soly
def example():
    N = 
    e = 
    c = 
    delta = .291 # this means that d < N^delta
    m = 4 # size of the lattice (bigger the better/slower)

    t = int((1-2*delta) * m)  # optimization from Herrmann and May
    X = 2*floor(N^delta)  # this _might_ be too much
    Y = floor(N^(1/2))    # correct if p, q are ~ same size
    P.<x,y> = PolynomialRing(ZZ)
    A = int((N+1)/2)
    pol = 1 + x * (A + y)
    if debug:
        print( "=== checking values ===")
        print( "* delta:", delta)
        print( "* delta < 0.292", delta < 0.292)
        print( "* size of e:", int(log(e)/log(2)))
        print( "* size of N:", int(log(N)/log(2)))
        print( "* m:", m, ", t:", t)

    if debug:
        print( "=== running algorithm ===")
        start_time = time.time()
    solx, soly = boneh_durfee(pol, e, m, t, X, Y)
    if solx > 0:
        print( "=== solution found ===")
        if False:
            print( "x:", solx)
            print( "y:", soly)

        d = int(pol(solx, soly) / e)
        m = pow(c,d,N)
        print( '[-]d is ' + str(d))
        print( '[-]m is: ' + str(m))
        print( '[-]hex(m) is: ' + '{:x}'.format(int(m)))
    else:
        print( "[!]no solution was found!")
        print( '[!]All Done!')

    if debug:
        print(("[!]Timer: %s s" % (time.time() - start_time)))
        print( '[!]All Done!')

if __name__ == "__main__":
    example()

3.End

这些RSA的破解都是难度较高的，后期还是需要多理解一下的。

文章作者: huangx607087
文章链接: http://example.com/2021/01/22/RSA-Notes4/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 huangx607087 !
Notes
赏
  目录