1. unusual rsa 系列

放在时至今日, 这几个考点应该说已经是常规范畴了
相关思路分析翅膀大佬博客有给出,详情可参考大佬博客
1.1. unusual rsa 1

sorce

    # ********************
    # @Author: Lazzaro
    # ********************

    from Crypto.Util.number import getPrime,bytes_to_long,long_to_bytes
    from random import randint
    from secret import flag

    p = getPrime(1024)
    q = getPrime(1024)
    n = p*q
    print(n)

    m = bytes_to_long(long_to_bytes(randint(0,30))*208+flag)
    assert(m.bit_length()==2044)
    print((m>>315)<<315)
    c = pow(m,3,n)
    print(c)

    #14113948189208713011909396304970377626324044633561155020366406284451614054260708934598840781397326960921718892801653205159753091559901114082556464576477585198060530094478860626532455065960136263963965819002575418616768412539016154873800614138683106056209070597212668250136909436974469812231498651367459717175769611385545792201291192023843434476550550829737236225181770896867698281325858412643953550465132756142888893550007041167700300621499970661661288422834479368072744930285128061160879720771910458653611076539210357701565156322144818787619821653007453741709031635862923191561438148729294430924288173571196757351837
    #1520800285708753284739523608878585974609134243280728660335545667177630830064371336150456537012842986526527904043383436211487979254140749228004148347597566264500276581990635110200009305900689510908049771218073767918907869112593870878204145615928290375086195098919355531430003571366638390993296583488184959318678321571278510231561645872308920917404996519309473979203661442792048291421574603018835698487725981963573816645574675640357569465990665689618997534740389987351864738104038598104713275375385003471306823348792559733332094774873827383320058176803218213042061965933143968710199376164960850951030741280074168795136
    #6635663565033382363211849843446648120305449056573116171933923595209656581213410699649926913276685818674688954045817246263487415328838542489103709103428412175252447323358040041217431171817865818374522191881448865227314554997131690963910348820833080760482835650538394814181656599175839964284713498394589419605748581347163389157651739759144560719049281761889094518791244702056048080280278984031050608249265997808217512349309696532160108250480622956599732443714546043439089844571655280770141647694859907985919056009576606333143546094941635324929407538860140272562570973340199814409134962729885962133342668270226853146819

Attacking RSA with small e by knowing parts of the message. coppersmith小e部分明文泄露攻击
$假设已知m的高位为M, 未知部分x_0, 则m=M+x_0. 如果x_0满足|x_0|\le N^{{\frac{1}{e}},} 那么可在多项式时间内恢复出x_0$
事实上, $x_0$不局限于低位,中间位置也是可以的
本题$x_0为315位,明显小于上界(2048//3 = 682)$

exp

    #exp.sage
    #coding:utf-8
    #已知明文的高位
    #https://sagecell.sagemath.org


    n = 
    e = 3
    beta = 1
    epsilon = 1/7
    nbits = n.nbits()
    kbits = floor(nbits*(beta^2/e-epsilon))
     
    mbar = 1520800285708753284739523608878585974609134243280728660335545667177630830064371336150456537012842986526527904043383436211487979254140749228004148347597566264500276581990635110200009305900689510908049771218073767918907869112593870878204145615928290375086195098919355531430003571366638390993296583488184959318678321571278510231561645872308920917404996519309473979203661442792048291421574603018835698487725981963573816645574675640357569465990665689618997534740389987351864738104038598104713275375385003471306823348792559733332094774873827383320058176803218213042061965933143968710199376164960850951030741280074168795136
     
    c = 6635663565033382363211849843446648120305449056573116171933923595209656581213410699649926913276685818674688954045817246263487415328838542489103709103428412175252447323358040041217431171817865818374522191881448865227314554997131690963910348820833080760482835650538394814181656599175839964284713498394589419605748581347163389157651739759144560719049281761889094518791244702056048080280278984031050608249265997808217512349309696532160108250480622956599732443714546043439089844571655280770141647694859907985919056009576606333143546094941635324929407538860140272562570973340199814409134962729885962133342668270226853146819
     
    print("upper %d bits (of %d bits) is given" % (nbits-kbits, nbits))
    PR.<x> = PolynomialRing(Zmod(n)) 
    f = (mbar + x)^e - c

    x0 = f.small_roots(X=2^kbits, beta=1)[0]
    m = int(mbar+x0)
    mhex = '%x'%m 
    print('hex m = ',mhex)
    mhex = '0'*(len(mhex)%2)+mhex
    print('str m = ', bytes.fromhex(mhex))

后记
- 在执行coppersmith已知明文泄露攻击时, 通常脚本会取$\epsilon=\frac{1}{7}$, 这时候sage的small_roots实际可恢复的$x_0上界为\frac{1}{2}N^{\frac{\beta2}{\delta}-\epsilon}\approx \frac{1}{2}N^{0.19}$
- 若使用sage中small_roots函数,在一定程度内通过减小epsilon的值, 可以提高上界大约到¼左右(e=3), 如何达到paper里的1/e可能需要其它实现方法
  1.2. unusual rsa 2

source

    # ********************
    # @Author: Lazzaro
    # ********************

    from Crypto.Util.number import getPrime,bytes_to_long,long_to_bytes
    from functools import reduce
    from secret import flag, x, y

    m = bytes_to_long(flag)
    p = getPrime(1024)
    q = getPrime(1024)
    n = p*q
    print(n)

    assert(reduce(lambda x,y:x&y,[(i-5)*i+6==0 for i in x]))
    assert(reduce(lambda x,y:x&y,[(j-15)*j+44==0 for j in y]))

    print(pow(reduce(lambda x,y:x*m+y,x),17,n))
    print(pow(reduce(lambda x,y:x*m+y,y),17,n))

    #23772599983135215481563178266884362291876571759991288577057472733374903836591330410574958472090396886895304944176208711481780781286891334062794555288959410390926474473859289842654809538435377431088422352076225067494924657598298955407771484146155998883073439266427190212827600119365643065276814044272790573450938596830336430371987561905132579730619341196199420897034988685012777895002554746080384319298123154671447844799088258541911028041717897434816921424155687677867019535399434825468160227242441375503664915265223696139025407768146464383537556265875013085702422829200814612395116961538432886116917063119749068212699
    #10900151504654409767059699202929100225155892269473271859207513720755903691031362539478242920144073599515746938827937863835169270383721094542639011665235593065932998091574636525973099426040452626893461449084383663453549354608769727777329036059746386523843912382289597182615339786437186169811342356085836838520978047561127661777189045888648773949147220411427306098338616422692914110656004863767719312410906124366000507952960331116878197129010412361636679449281808407214524741732730279777729251515759320442591663641984363061618865267606007355576230009922421807527598213455112981354590909603317525854070358390622096569841
    #17298679220717326374674940612143058330715465693318467692839033642321129433471254547497087746971317567301086124779289015934582615377165560688447452762043163082394944604062014490446763247008217251611443338103074143809936437694543761369945095202092750900940979469994907399829695696313513303922266742415376818434932335640062684245008822643258497589196668426788916969378417960200705779461808292296450298558001909603602502604228973101048082095642290047196235959438278631661658312398313171590515776453711432353011579809351076532129444735206408591345372296372378396539831385036814349328459266432393612919118094115543053115450

首先求得x和y的值(简单,略)
```
    x = [2,3]
    y = [4,11]
```
可知实际上已知明文的两个线性关系对应的密文
- $m_1^{17} = c_1\ mod\ N, m_1=2m+3$
- $m_2^{17} = c_2\ mod\ N,m_2=4m+11$
使用FR相关攻击
- 首先考虑$m_2 = m_1+d（d已知）的情况$
- $m_1^e = c_1\ mod\ N$
- $m_2^e = (m_1+d)^e =c_2\ mod\ N$
- 则多项式$f_1=x_1^e - c_1\ mod\ N与f_2=(x_1+d)^e-c_2\ mod\ N有共同的一个根m_1$
- 也就是有共同的因式$(x-m_1), 所以只需对f_1\ f_2求多项式gcd即可恢复出m_1$
- 然后考虑$m_2 = km_1+d（k,d已知）的情况$
- 由于RSA满足乘法同态,$不妨令m_1′=km_1,可先求c_1′ = (m_1′)^e\ mod\ N = ((k^e\ mod\ N)\cdot c_1)\ mod\ N$
- 问题转化为上述已知d的情况, $m_2=m_1′+d$
- 求得$m_1′之后, 乘上逆元即可恢复出m=k^{-1}\cdot m_1′\ mod\ N$
- 问题还可以进一步扩展,这里不再展开
exp过程:
- 由于$m_2 = 2m_1+5= (4m+6) +5$
- 可利用FR相关攻击求得$m_1′=4m+6,则m = (m_1′-6)\cdot 4^{-1}\ mod\ N$

exp:多项式求GCD的部分sage有现成的实现可以用，懒得开sage了，在Python里手写了一个

    #exp.py

    #FR相关攻击
    def related_message_attack(c1,c2, di, e,n):
        from Crypto.Util.number import GCD
        #展开(x+a)^e的系数,杨辉三角
        def poly_coef(a, e):
            assert e >= 0
            if e == 0:
                return 1
            elif e == 1:
                return [1,1]
            else:
                res = [1]
                coe_prev = poly_coef(a, e-1)
                for i in range(len(coe_prev)-1):
                    res.append(sum(coe_prev[i:i+2]))
                res.append(1)
                return res

        def poly_extend(a, e, n,c):
            coef = poly_coef(a, e)
            res = [a**i * coef[i] for i in range(len(coef))]

            res[-1] = res[-1] + c
            res = [x%n for x in res]

            return res
            
        #化首1
        def poly_monic(pl,n):
            from gmpy2 import invert
            for p in pl:
                if p!=0:
                    inv = invert(p,n)
                    break
            return [int((x*inv)%n) for x in pl]

        #模运算,这部分写的不是很好,待优化
        def poly_mod(pl1,pl2,n):
            from functools import reduce
            assert len(pl1) == len(pl2)
            pl1 = poly_monic(pl1,n)
            pl2 = poly_monic(pl2,n)
            for i in range(len(pl1)):
                if pl1[i] > pl2[i]:
                    break
                elif pl1[i] < pl2[i]:
                    return poly_mod(pl2,pl1,n)
            else:
                return 0
            idx = -1
            for i in range(len(pl1)):
                if pl1[i] == 1:
                    idx = i
                    break
            for i in range(idx,len(pl2)):
                if pl2[i] == 1:
                    pl2 = pl2[:idx] + pl2[i:]
                    pl2 += [0]*(len(pl1)-len(pl2))
                    break
            
            res = []
            for i in range(len(pl1)):
                if pl2[i] == 0:
                    res.append(pl1[i])
                else:
                    res.append(pl1[i]-pl2[i])
            
            res = [int(x%n) for x in res]
            g = int(reduce(GCD,res))
            if g > 1:
                res = [x//g for x in res]
            return res
        #最大公因式
        def poly_gcd(pl1,pl2,n):
            while pl2 != 0:
                pl1,pl2 = pl2, poly_mod(pl1,pl2,n)
            pl1 = poly_monic(pl1,n)

            return pl1

        #x^e-c1
        #(x+di)^e-c2
        pl1 = poly_extend(0,e,n,-c1)
        pl2 = poly_extend(di,e,n,-c2)

        pl_d = poly_gcd(pl1,pl2,n)

        #求得(x-m),所以取负数即为m
        m = n - pl_d[-1]
        return m



    def exp():
        from Crypto.Util.number import inverse, long_to_bytes, bytes_to_long
        n = 23772599983135215481563178266884362291876571759991288577057472733374903836591330410574958472090396886895304944176208711481780781286891334062794555288959410390926474473859289842654809538435377431088422352076225067494924657598298955407771484146155998883073439266427190212827600119365643065276814044272790573450938596830336430371987561905132579730619341196199420897034988685012777895002554746080384319298123154671447844799088258541911028041717897434816921424155687677867019535399434825468160227242441375503664915265223696139025407768146464383537556265875013085702422829200814612395116961538432886116917063119749068212699
        c1 = 10900151504654409767059699202929100225155892269473271859207513720755903691031362539478242920144073599515746938827937863835169270383721094542639011665235593065932998091574636525973099426040452626893461449084383663453549354608769727777329036059746386523843912382289597182615339786437186169811342356085836838520978047561127661777189045888648773949147220411427306098338616422692914110656004863767719312410906124366000507952960331116878197129010412361636679449281808407214524741732730279777729251515759320442591663641984363061618865267606007355576230009922421807527598213455112981354590909603317525854070358390622096569841
        c2 = 17298679220717326374674940612143058330715465693318467692839033642321129433471254547497087746971317567301086124779289015934582615377165560688447452762043163082394944604062014490446763247008217251611443338103074143809936437694543761369945095202092750900940979469994907399829695696313513303922266742415376818434932335640062684245008822643258497589196668426788916969378417960200705779461808292296450298558001909603602502604228973101048082095642290047196235959438278631661658312398313171590515776453711432353011579809351076532129444735206408591345372296372378396539831385036814349328459266432393612919118094115543053115450
        e = 17
        c11 = (pow(2,e,n) * c1) % n
        diff = 5
        m1 = related_message_attack(c11, c2, diff, e, n)
        print("4m+6 =", m1)
        m = (m1 - 6) * inverse(4,n) % n
        print(long_to_bytes(m))

    if __name__ == '__main__':
        exp()

1.3. unusual rsa 3

常规多项式rsa, 分解N求解,还没仔细研究

exp

    #多项式rsa

    def main():

        p = 2470567871
        R.<x> = PolynomialRing(GF(p))

        N = 1932231392*x^255 + 1432733708*x^254 + 1270867914*x^253 + 1573324635*x^252 + 2378103997*x^251 + 820889786*x^250 + 762279735*x^249 + 1378353578*x^248 + 1226179520*x^247 + 657116276*x^246 + 1264717357*x^245 + 1015587392*x^244 + 849699356*x^243 + 1509168990*x^242 + 2407367106*x^241 + 873379233*x^240 + 2391647981*x^239 + 517715639*x^238 + 828941376*x^237 + 843708018*x^236 + 1526075137*x^235 + 1499291590*x^234 + 235611028*x^233 + 19615265*x^232 + 53338886*x^231 + 434434839*x^230 + 902171938*x^229 + 516444143*x^228 + 1984443642*x^227 + 966493372*x^226 + 1166227650*x^225 + 1824442929*x^224 + 930231465*x^223 + 1664522302*x^222 + 1067203343*x^221 + 28569139*x^220 + 2327926559*x^219 + 899788156*x^218 + 296985783*x^217 + 1144578716*x^216 + 340677494*x^215 + 254306901*x^214 + 766641243*x^213 + 1882320336*x^212 + 2139903463*x^211 + 1904225023*x^210 + 475412928*x^209 + 127723603*x^208 + 2015416361*x^207 + 1500078813*x^206 + 1845826007*x^205 + 797486240*x^204 + 85924125*x^203 + 1921772796*x^202 + 1322682658*x^201 + 2372929383*x^200 + 1323964787*x^199 + 1302258424*x^198 + 271875267*x^197 + 1297768962*x^196 + 2147341770*x^195 + 1665066191*x^194 + 2342921569*x^193 + 1450622685*x^192 + 1453466049*x^191 + 1105227173*x^190 + 2357717379*x^189 + 1044263540*x^188 + 697816284*x^187 + 647124526*x^186 + 1414769298*x^185 + 657373752*x^184 + 91863906*x^183 + 1095083181*x^182 + 658171402*x^181 + 75339882*x^180 + 2216678027*x^179 + 2208320155*x^178 + 1351845267*x^177 + 1740451894*x^176 + 1302531891*x^175 + 320751753*x^174 + 1303477598*x^173 + 783321123*x^172 + 1400145206*x^171 + 1379768234*x^170 + 1191445903*x^169 + 946530449*x^168 + 2008674144*x^167 + 2247371104*x^166 + 1267042416*x^165 + 1795774455*x^164 + 1976911493*x^163 + 167037165*x^162 + 1848717750*x^161 + 573072954*x^160 + 1126046031*x^159 + 376257986*x^158 + 1001726783*x^157 + 2250967824*x^156 + 2339380314*x^155 + 571922874*x^154 + 961000788*x^153 + 306686020*x^152 + 80717392*x^151 + 2454799241*x^150 + 1005427673*x^149 + 1032257735*x^148 + 593980163*x^147 + 1656568780*x^146 + 1865541316*x^145 + 2003844061*x^144 + 1265566902*x^143 + 573548790*x^142 + 494063408*x^141 + 1722266624*x^140 + 938551278*x^139 + 2284832499*x^138 + 597191613*x^137 + 476121126*x^136 + 1237943942*x^135 + 275861976*x^134 + 1603993606*x^133 + 1895285286*x^132 + 589034062*x^131 + 713986937*x^130 + 1206118526*x^129 + 311679750*x^128 + 1989860861*x^127 + 1551409650*x^126 + 2188452501*x^125 + 1175930901*x^124 + 1991529213*x^123 + 2019090583*x^122 + 215965300*x^121 + 532432639*x^120 + 1148806816*x^119 + 493362403*x^118 + 2166920790*x^117 + 185609624*x^116 + 184370704*x^115 + 2141702861*x^114 + 223551915*x^113 + 298497455*x^112 + 722376028*x^111 + 678813029*x^110 + 915121681*x^109 + 1107871854*x^108 + 1369194845*x^107 + 328165402*x^106 + 1792110161*x^105 + 798151427*x^104 + 954952187*x^103 + 471555401*x^102 + 68969853*x^101 + 453598910*x^100 + 2458706380*x^99 + 889221741*x^98 + 320515821*x^97 + 1549538476*x^96 + 909607400*x^95 + 499973742*x^94 + 552728308*x^93 + 1538610725*x^92 + 186272117*x^91 + 862153635*x^90 + 981463824*x^89 + 2400233482*x^88 + 1742475067*x^87 + 437801940*x^86 + 1504315277*x^85 + 1756497351*x^84 + 197089583*x^83 + 2082285292*x^82 + 109369793*x^81 + 2197572728*x^80 + 107235697*x^79 + 567322310*x^78 + 1755205142*x^77 + 1089091449*x^76 + 1993836978*x^75 + 2393709429*x^74 + 170647828*x^73 + 1205814501*x^72 + 2444570340*x^71 + 328372190*x^70 + 1929704306*x^69 + 717796715*x^68 + 1057597610*x^67 + 482243092*x^66 + 277530014*x^65 + 2393168828*x^64 + 12380707*x^63 + 1108646500*x^62 + 637721571*x^61 + 604983755*x^60 + 1142068056*x^59 + 1911643955*x^58 + 1713852330*x^57 + 1757273231*x^56 + 1778819295*x^55 + 957146826*x^54 + 900005615*x^53 + 521467961*x^52 + 1255707235*x^51 + 861871574*x^50 + 397953653*x^49 + 1259753202*x^48 + 471431762*x^47 + 1245956917*x^46 + 1688297180*x^45 + 1536178591*x^44 + 1833258462*x^43 + 1369087493*x^42 + 459426544*x^41 + 418389643*x^40 + 1800239647*x^39 + 2467433889*x^38 + 477713059*x^37 + 1898813986*x^36 + 2202042708*x^35 + 894088738*x^34 + 1204601190*x^33 + 1592921228*x^32 + 2234027582*x^31 + 1308900201*x^30 + 461430959*x^29 + 718926726*x^28 + 2081988029*x^27 + 1337342428*x^26 + 2039153142*x^25 + 1364177470*x^24 + 613659517*x^23 + 853968854*x^22 + 1013582418*x^21 + 1167857934*x^20 + 2014147362*x^19 + 1083466865*x^18 + 1091690302*x^17 + 302196939*x^16 + 1946675573*x^15 + 2450124113*x^14 + 1199066291*x^13 + 401889502*x^12 + 712045611*x^11 + 1850096904*x^10 + 1808400208*x^9 + 1567687877*x^8 + 2013445952*x^7 + 2435360770*x^6 + 2414019676*x^5 + 2277377050*x^4 + 2148341337*x^3 + 1073721716*x^2 + 1045363399*x + 1809685811

        S.<x> = R.quotient(N)
        c = 922927962*x^254 + 1141958714*x^253 + 295409606*x^252 + 1197491798*x^251 + 2463440866*x^250 + 1671460946*x^249 + 967543123*x^248 + 119796323*x^247 + 1172760592*x^246 + 770640267*x^245 + 1093816376*x^244 + 196379610*x^243 + 2205270506*x^242 + 459693142*x^241 + 829093322*x^240 + 816440689*x^239 + 648546871*x^238 + 1533372161*x^237 + 1349964227*x^236 + 2132166634*x^235 + 403690250*x^234 + 835793319*x^233 + 2056945807*x^232 + 480459588*x^231 + 1401028924*x^230 + 2231055325*x^229 + 1716893325*x^228 + 16299164*x^227 + 1125072063*x^226 + 1903340994*x^225 + 1372971897*x^224 + 242927971*x^223 + 711296789*x^222 + 535407256*x^221 + 976773179*x^220 + 533569974*x^219 + 501041034*x^218 + 326232105*x^217 + 2248775507*x^216 + 1010397596*x^215 + 1641864795*x^214 + 1365178317*x^213 + 1038477612*x^212 + 2201213637*x^211 + 760847531*x^210 + 2072085932*x^209 + 168159257*x^208 + 70202009*x^207 + 1193933930*x^206 + 1559162272*x^205 + 1380642174*x^204 + 1296625644*x^203 + 1338288152*x^202 + 843839510*x^201 + 460174838*x^200 + 660412151*x^199 + 716865491*x^198 + 772161222*x^197 + 924177515*x^196 + 1372790342*x^195 + 320044037*x^194 + 117027412*x^193 + 814803809*x^192 + 1175035545*x^191 + 244769161*x^190 + 2116927976*x^189 + 617780431*x^188 + 342577832*x^187 + 356586691*x^186 + 695795444*x^185 + 281750528*x^184 + 133432552*x^183 + 741747447*x^182 + 2138036298*x^181 + 524386605*x^180 + 1231287380*x^179 + 1246706891*x^178 + 69277523*x^177 + 2124927225*x^176 + 2334697345*x^175 + 1769733543*x^174 + 2248037872*x^173 + 1899902290*x^172 + 409421149*x^171 + 1223261878*x^170 + 666594221*x^169 + 1795456341*x^168 + 406003299*x^167 + 992699270*x^166 + 2201384104*x^165 + 907692883*x^164 + 1667882231*x^163 + 1414341647*x^162 + 1592159752*x^161 + 28054099*x^160 + 2184618098*x^159 + 2047102725*x^158 + 103202495*x^157 + 1803852525*x^156 + 446464179*x^155 + 909116906*x^154 + 1541693644*x^153 + 166545130*x^152 + 2283548843*x^151 + 2348768005*x^150 + 71682607*x^149 + 484339546*x^148 + 669511666*x^147 + 2110974006*x^146 + 1634563992*x^145 + 1810433926*x^144 + 2388805064*x^143 + 1200258695*x^142 + 1555191384*x^141 + 363842947*x^140 + 1105757887*x^139 + 402111289*x^138 + 361094351*x^137 + 1788238752*x^136 + 2017677334*x^135 + 1506224550*x^134 + 648916609*x^133 + 2008973424*x^132 + 2452922307*x^131 + 1446527028*x^130 + 29659632*x^129 + 627390142*x^128 + 1695661760*x^127 + 734686497*x^126 + 227059690*x^125 + 1219692361*x^124 + 635166359*x^123 + 428703291*x^122 + 2334823064*x^121 + 204888978*x^120 + 1694957361*x^119 + 94211180*x^118 + 2207723563*x^117 + 872340606*x^116 + 46197669*x^115 + 710312088*x^114 + 305132032*x^113 + 1621042631*x^112 + 2023404084*x^111 + 2169254305*x^110 + 463525650*x^109 + 2349964255*x^108 + 626689949*x^107 + 2072533779*x^106 + 177264308*x^105 + 153948342*x^104 + 1992646054*x^103 + 2379817214*x^102 + 1396334187*x^101 + 2254165812*x^100 + 1300455472*x^99 + 2396842759*x^98 + 2398953180*x^97 + 88249450*x^96 + 1726340322*x^95 + 2004986735*x^94 + 2446249940*x^93 + 520126803*x^92 + 821544954*x^91 + 1177737015*x^90 + 676286546*x^89 + 1519043368*x^88 + 224894464*x^87 + 1742023262*x^86 + 142627164*x^85 + 1427710141*x^84 + 1504189919*x^83 + 688315682*x^82 + 1397842239*x^81 + 435187331*x^80 + 433176780*x^79 + 454834357*x^78 + 1046713282*x^77 + 1208458516*x^76 + 811240741*x^75 + 151611952*x^74 + 164192249*x^73 + 353336244*x^72 + 1779538914*x^71 + 1489144873*x^70 + 213140082*x^69 + 1874778522*x^68 + 908618863*x^67 + 1058334731*x^66 + 1706255211*x^65 + 708134837*x^64 + 1382118347*x^63 + 2111915733*x^62 + 1273497300*x^61 + 368639880*x^60 + 1652005004*x^59 + 1977610754*x^58 + 1412680185*x^57 + 2312775720*x^56 + 59793381*x^55 + 1345145822*x^54 + 627534850*x^53 + 2159477761*x^52 + 10450988*x^51 + 1479007796*x^50 + 2082579205*x^49 + 1158447154*x^48 + 126359830*x^47 + 393411272*x^46 + 2343384236*x^45 + 2191577465*x^44 + 1281188680*x^43 + 230049708*x^42 + 539600199*x^41 + 1711135601*x^40 + 1659775448*x^39 + 1716176055*x^38 + 904363231*x^37 + 2385749710*x^36 + 567278351*x^35 + 404199078*x^34 + 372670353*x^33 + 1286079784*x^32 + 1744355671*x^31 + 2316856064*x^30 + 2106475476*x^29 + 614988454*x^28 + 2149964943*x^27 + 1065233185*x^26 + 188130174*x^25 + 540415659*x^24 + 1031409799*x^23 + 1067085678*x^22 + 1005161755*x^21 + 249654085*x^20 + 1816791634*x^19 + 1437500292*x^18 + 448596413*x^17 + 2397497659*x^16 + 2353732701*x^15 + 2068949189*x^14 + 1826419168*x^13 + 1265366199*x^12 + 547031306*x^11 + 1016962374*x^10 + 160089486*x^9 + 2264803979*x^8 + 1081806194*x^7 + 824215340*x^6 + 497731793*x^5 + 45017166*x^4 + 317548920*x^3 + 1391127733*x^2 + 1752881284*x + 1290424106

        
        P, Q = N.factor()
        P, Q = P[0], Q[0]
        phi = (p**P.degree()-1)*(p**Q.degree()-1)
        e = 0x10001
        d = inverse_mod(e, phi)

        m = c^d
        m = "".join([chr(c) for c in m.list()])
        print(m)


    if __name__ == '__main__':
        main()

1.4. unusual rsa 4

source

    from Crypto.Util.number import getPrime,bytes_to_long,long_to_bytes
    from gmpy2 import invert
    from secret import flag

    m = bytes_to_long(flag)
    p = getPrime(1024)
    q = getPrime(1024)
    n = p*q
    print(invert(q,p))

    e = 0x10001
    d = invert(e,(p-1)*(q-1))
    print(d)

    c = pow(m,e,n)
    print(c)


        #113350138578125471637271827037682321496361317426731366252238155037440385105997423113671392038498349668206564266165641194668802966439465128197299073392773586475372002967691512324151673246253769186679521811837698540632534357656221715752733588763108463093085549826122278822507051740839450621887847679420115044512
        #27451162557471435115589774083548548295656504741540442329428952622804866596982747294930359990602468139076296433114830591568558281638895221175730257057177963017177029796952153436494826699802526267315286199047856818119832831065330607262567182123834935483241720327760312585050990828017966534872294866865933062292893033455722786996125448961180665396831710915882697366767203858387536850040283296013681157070419459208544201363726008380145444214578735817521392863391376821427153094146080055636026442795625833039248405951946367504865008639190248509000950429593990524808051779361516918410348680313371657111798761410501793645137
        #619543409290228183446186073184791934402487500047968659800765382797769750763696880547221266055431306972840980865602729031475343233357485820872268765911041297456664938715949124290204230537793877747551374176167292845717246943780371146830637073310108630812389581197831196039107931968703635129091224513813241403591357678410312272233389708366642638825455844282490676862737715585788829936919637988039113463707959069907015464745700766013573282604376277598510224455044288896809217461295080140187509519005245601483583507547733673523120385089098002298314719617693895392148294399937798485146568296114338393548124451378170302291

分析过程大佬博客已经很详细,这里不再赘述,仅做简要分析
简单来说,就是已知$q^{-1} mod\ p, 和d恢复p,q的攻击$,使用类似于已知n,e,d分解n的思路
$设x=q^{-1}\ mod\ p$
$由\phi=(p-1)\cdot(q-1)=N - (p+q)+1$ , 模上p
$\phi\ mod\ p = -q+1\ mod\ p$ , 乘以x,有
$x\cdot\phi \equiv -xq + x \equiv -1+x\ mod\ p$
从而$x\phi-x+1\equiv0\ mod\ p,即 x\phi-x+1为p的倍数$
不妨令$k_p=x\cdot\phi-x+1$
$对任意的g,(g,p)=1, 有g^\phi \equiv1\ mod\ p\rightarrow (g^\phi\ mod\ k_p) \equiv1\ mod\ p$
$即(g^\phi mod\ k_p)-1为p的倍数$,那么只需求得多个值,取GCD即可

exp

    from Crypto.Util.number import getPrime,bytes_to_long,long_to_bytes
    from gmpy2 import invert

    def exp():
        from gmpy2 import gcd,next_prime
        e = 0x10001
        x = 113350138578125471637271827037682321496361317426731366252238155037440385105997423113671392038498349668206564266165641194668802966439465128197299073392773586475372002967691512324151673246253769186679521811837698540632534357656221715752733588763108463093085549826122278822507051740839450621887847679420115044512
        d = 27451162557471435115589774083548548295656504741540442329428952622804866596982747294930359990602468139076296433114830591568558281638895221175730257057177963017177029796952153436494826699802526267315286199047856818119832831065330607262567182123834935483241720327760312585050990828017966534872294866865933062292893033455722786996125448961180665396831710915882697366767203858387536850040283296013681157070419459208544201363726008380145444214578735817521392863391376821427153094146080055636026442795625833039248405951946367504865008639190248509000950429593990524808051779361516918410348680313371657111798761410501793645137
        c = 619543409290228183446186073184791934402487500047968659800765382797769750763696880547221266055431306972840980865602729031475343233357485820872268765911041297456664938715949124290204230537793877747551374176167292845717246943780371146830637073310108630812389581197831196039107931968703635129091224513813241403591357678410312272233389708366642638825455844282490676862737715585788829936919637988039113463707959069907015464745700766013573282604376277598510224455044288896809217461295080140187509519005245601483583507547733673523120385089098002298314719617693895392148294399937798485146568296114338393548124451378170302291

        ed = e*d
        for i in range(1,e-1):
            if (ed-1) % i == 0:
                phi = (ed-1)//i
                kp = x*phi - x + 1
                tp = []
                g = 3
                for j in range(999):
                    t = pow(g,phi,kp) - 1
                    if t > 0 and (t not in tp):
                        tp.append(t)
                    g = next_prime(g)
                    if len(tp) >= 2:
                        break
                if len(tp) >= 2:
                    p = gcd(tp[0],tp[1])
                    print(i,'p = ',p)
                    if gcd(x,p) != 1 or p < x:
                        continue
                    else:
                        break
        q = invert(x,p)
        n = p*q
        m = pow(c,d,n)
        print(long_to_bytes(m))
                    

    if __name__ == '__main__':
        exp()

1.5. unusual rsa 5

有限域开方的问题,AMM算法
求得所有mod p和mod q的根之后,使用剩余定理求出所有可能值
求单个根:
- $x^e\equiv c\ mod\ p$其中p,e为素数
- $把p-1写成p-1=e^t\cdot s,(e,s)=1事实上当t=1时,可以很轻易的求出一个根$
- $若t=1, 则p-1=e\cdot s,(e,s)=1$
- $记\delta \equiv\ c\ mod\ p,则x^{p-1}=x{es}\equiv \delta^s \equiv 1\ mod\ p$
- $取\alpha=r^{-1}\ mod\ s,则有s|(\alpha\cdot r-1)\rightarrow\alpha r-1=ks$
- $即\delta^{\alpha r-1}\equiv 1\ mod\ p\rightarrow(\delta^\alpha)^r\equiv \delta\ mod\ p$
- $求得\delta^{\alpha即为一个根$}
求所有的根:
- 利用上一步求出的一个根,记作$x_0$
- 取一些小素数$g \in {3,5,7….}(这里满足(g,p)=1即可,我比较习惯取小素数)$
- $求d=g^{{\frac{\phi}{e}}\} mod\ p, 显然d^e\equiv1\ mod\ p$
- 可知$x’\equiv x_0\cdot d\ mod\ q$也是满足$x^e\equiv c\ mod\ p$的根
- 反复求不重复的e个根即可
本题中$e=20=2^2\cdot 5$
- 可先求5次方根,然后分别求两次2次方根
- 其实由于m足够小也没有填充,求完5次方根直接用iroot开4次方也可求出flag
后记:
- 其实当t>1时,也不复杂,paper里写的很清楚了,这里不再赘述分析,仅给出脚本

exp:

    #解剩余定理,r=[余数],m=[模数]
    def crt(r, m):
        from functools import reduce
        from Crypto.Util.number import inverse
        from operator import mul

        assert len(r) == len(m)
        M = reduce(lambda x,y:x*y, m)
        #M = [M//mi for mi in m]
        t = [inverse(M//x,x)*(M//x) for x in m]
        res = sum(map(mul,r,t)) % M
        return res

    #求解x^e = c mod p^order
    def nthRoot_amm(c,e,p,order=1):
        from gmpy2 import is_prime
        from Crypto.Util.number import getRandomRange, inverse, GCD

        assert is_prime(p) and is_prime(e) and (p-1)%e==0

        cp = c%p**order if c>p**order else c
        phi = (p - 1) * p**(order-1)
        mod = p**order
        for i in range(9999):
            rho = getRandomRange(1, mod)
            if pow(rho, phi // e, mod) != 1:
                #print(f'i = {i}')
                break
        s = phi
        t = 0
        while s % e == 0:
            s //= e
            t += 1
        assert GCD(s, e) == 1
        #print(f't = {t} ')
        alpha = inverse(e, s)
        a = pow(rho, s*e**(t-1), mod)
        b = pow(cp, e*alpha-1, mod)
        c = pow(rho, s, mod)
        h = 1

        for i in range(1, t):
            d = pow(b, e**(t-1-i), mod)
            if d == 1:
                j = 0
            else:
                j = e - next(filter(lambda x: pow(a,x,mod)==d, range(e)))
            b = b * pow(c, e*j, mod) % mod
            h = h * pow(c, j, mod) % mod
            c = pow(c, e, mod)
        
        root = pow(cp, alpha, mod) * h % mod

        #找到其它根
        from gmpy2 import next_prime
        all_roots = set()
        all_roots.add(root)
        g = 3
        while len(all_roots) < e:
            newRoot = root
            g = int(next_prime(g))
            u =  pow(g, phi//e, mod)
            for i in range(e-1):
                newRoot = (newRoot * u) % mod
                all_roots.add(newRoot)
        
        return list(all_roots)


    def expUnrsa5():
        from Crypto.Util.number import GCD, long_to_bytes
        from itertools import product
        from gmpy2 import iroot
        e = 0x14
        p = 733089589724903586073820965792963746076789390539824437962807679954808310072656817423828613938510684864567664345751164944269489647964227519307980688068059059377123391499328155025962198363435968318689113750910755244276996554328840879221120846257832190569086861774466785101694608744384540722995426474322431441
        q = 771182695213910447650732428220054698293987458796864628535794956332865106301119308051373568460701145677164052375651484670636989109023957702790185901445649197004100341656188532246838220216919835415376078688888076677350412398198442910825884505318258393640994788407100699355386681624118606588957344077387058721
        n = p*q
        c = 406314720119562590605554101860453913891646775958515375190169046313074168423687276987576196367702523895650602252851191274766072774312855212771035294337840170341052016067631007495713764510925931612800335613551752201920460877432379214684677593342046715833439574705829048358675771542989832566579493199671622475225225451781214904100440695928239014046619329247750637911015313431804069312072581674845078940868349474663382442540424342613429896445329365750444298236684237769335405534090013035238333534521759502103604033307768304224154383880727399879024077733935062478113298538634071453067782212909271392163928445051705642
        print('gcd(e,p-1)',GCD(e,p-1))
        print('gcd(e,q-1',GCD(e,q-1))
        e1 = 5
        cp1 = nthRoot_amm(c,e1,p)
        cq1 = nthRoot_amm(c,e1,q)
        cp1 = [nthRoot_amm(x,2,p) for x in cp1]
        cq1 = [nthRoot_amm(x,2,q) for x in cq1]
        mp = []
        mq = []
        for cp in cp1:
            for cpp in cp:
                mp.extend(nthRoot_amm(cpp,2,p))
        for cq in cq1:
            for cqq in cq:
                mq.extend(nthRoot_amm(cqq,2,q))
        for m1,m2 in product(mp,mq):
            m = crt([m1,m2],[p,q])
            flag = long_to_bytes(m)
            if b'flag' in flag:
                print(flag)
                break

    if __name__ == '__main__':
        expUnrsa5()

2. 密码挑战系列

2.1. 真·Beginner

这题还真没做出来
2.2. 真·guessguess
利用已知的部分明文,使用z3求出key,然后解密即可
2.3. Lousy RSA
盲猜flag格式为flag{.*}那么第一位为f第二位为l
利用同余关系求出r,然后逐位爆破即可
部分exp
```
    ct = c[0]
    c0 = c[1] 
    c1 = c[2]

    m0 = ord('f')
    m0 = pow(m0,3,n)
    m1 = ord('l')
    m1 = pow(m1,3,n)

    c0 = (c0 - pow(m0,3,n) - ct) * invert(3,n) * invert(m0,n) % n
    c1 = (c1 - pow(m1,3,n) - ct) * invert(3,n) * invert(m1,n) % n
    b0 = invert(m0,n) * m0**2 % n
    b1 = invert(m1,n) * m1**2 % n
    r = (c0 - c1) * invert(b0-b1,n) % n
```
2.4. Not That Right Use
- 做出来之后发现可能是非预期解,因为flag为flag{NTRU_..........}
- 这里分享下我的解法
- 分析可知,解密的关键在于f和g必须小于一定的值,从而使得gr+mf<q
- 只要f和g足够小,就可以完成解密,并不需要使用加密时候的值
- f,h,g,q四个数满足关系:
- $f\cdot h = g\ mod\ q$
- h和q是已知确定的
- 可以通过辗转取余的方法,来约束g的值,从而求出f的值
- 部分exp
```
    s = q % h
    g = h % s

    for i in range(10000):
        g, s = g%s, s%g
        if g <2**4000:
            print(i)
            break

    f = h * gmpy2.invert(g,q) % q
    f = gmpy2.invert(f,q)
    d = gmpy2.gcd(f,g)
    assert d == 1

    flen = len(f"{f:b}")
    print('flen =',flen)

    print(decrypt(c,f,g,h,q))
```
  2.5. so Damn big e?
- 这里走了不少弯路
- e除了过小意外,e再大都是没有攻击方式的,有攻击方式只可能是d出了问题
- 这题三组n,e,c根据提示, 为共享d攻击
- 没仔细研究,直接抄的脚本
- 部分exp
```
    #sage
    n = [n0,n1,n2]
    e = [e0,e1,e2]
    c = [c0,c1,c2]
    M = isqrt(max(n))
    A = Matrix(ZZ, len(e) + 1, len(e) + 1)
    A[0] = [M] + e
    for i in range(len(e)):
        A[i + 1, i + 1] = -n[i]
    AL = A.BKZ()

    d = abs(AL[0, 0]) // M
    print(f'found d with {d.nbits()} bits')
    print(long_to_bytes(pow(c[0], d, n[0])))
```
  2.6. Hammingway
- 直接爆破翻转, parity一致即为正确的值
- 部分exp
```
    def unparity(slist):
        res = ''
        res = [slist[2]] + slist[4:7] + slist[8:]
        return ''.join(res)

    def strparity(slist):
        for i in [0,1,3,7]:
            slist[i] = '0'
        parity = reduce(lambda a, b: a^b, [j+1 for j, bit in enumerate(slist) if int(bit)])
        parity = list(reversed(list(str(format(parity, "04b")))))
        return parity

    def exp():
        from itertools import product
        c = open("enc", "r").read()
        c = [list(c[i:i+15]) for i in range(0,len(c),15)]

        strBin = ''
        for cc in c:
            for idx in range(len(cc)):
                flip_cc = cc.copy()
                flip_cc[idx] = str(1^int(flip_cc[idx]))
                p1 = flip_cc[:2] + [flip_cc[3]] + [flip_cc[7]]
                p2 = strparity(flip_cc)
                if p1 == p2:
                    strBin +=unparity(flip_cc)
                    break

        plain_str = ''.join([chr(int(strBin[i:i+8],2)) for i in range(0,len(strBin),8)])
        print(plain_str)

    if __name__ == '__main__':
        exp()
```
  2.7. ^o
- 简单,略
  2.8. rsa-rsa-rsa-rsa
- 这题可能也是非预期解
- 直接套的类似d泄露的方法,解同余方程组, 感觉有点傻
- 四个方程跑出来几分钟到一个小时不等..
- 主要也是太菜了,没想到别的更好的方法
- 部分exp
```
    #sage
    def find_p(d0, kbits, e, n,r=1):
        X = var('X')
        nn = n//r
        assert nn * r == n
        for k in range(1, e+1):
            results = solve_mod([e*d0*X - k*(r-1)*(nn*X-X^2-nn+X) == X], 2^kbits)
            #results = solve_mod([e*d0*X - k*X*(n-X+1) + k*n == X], 2^kbits)#p700*q1400
            #results = solve_mod([e*d0*X - k*(X*nn-nn-X^2+X)*(r-1)== X], 2^kbits)
            for x in results:
                p0 = ZZ(x[0])
                print(k,'p0 = ',p0.nbits(),gcd(p0,nn))
                if gcd(p0,nn) != 1:
                    return p0


    if __name__ == '__main__':
        e = 1667
        c = 4863472644674217870502565424693713184000486927536995099651919590240866271469253214344182197334842137507506086858073884082195321114866653889949375924127756080834433032454456087411507323678798402153608823661022078160023141062260191255620270915331691502139415828179122879192294099884444457864136735926806260011876510858736421882145300532909608975279197160825647548849553174913916658119199697996174288038879828745214652265872117421930778762203853307243931789294163101430752597851152391642867666313642265617715322464199460030394197177929755093316075034884004768661209784916266357741690678348488199658622049287166258613947571770322996041
        beta = 0.5

        n = 3131941372466165986449739075865674968940174516444076890636643699669723723624476772239531739488887900237270630167942798909976360814710578884208330959980913704031373375334097086496506714284879981190426211509126158904765890049203697875840397068619455247802512255186427221538191894428225298900004231340034286465730171834031703088563214778317659451882235661464904425245012884275748455326419836548780784469413852141646848930684399793701878360640328085712887402813460070572277272227166256367362553115896571208152861417127327011927963063263882998956777761230189213433480309856104225339302750882900096482310202396770196005219615987514591
        r = 304638331320481268163138611517965845496568256221655432858547689589115159924032407549669321779378717473668562428569960589364902228881784141496830122429070596778200772640542355062106843431507096043904169247235421
        d0 = 6868327978266104802989981973163703169084555636189784576185238791210063194494388661448473806872716472633244760268088234379444819398858802986829208689016378717268858566806477769143597241086404105945418733687540225015490422345056492001144261514258758982987176876603622870246393409441550222724784227760607803005148775595

        d0 = d0 % 2**700
        nbits = n.nbits()
        kbits = d0.nbits()
        #kbits = 1050

        print("lower %d bits (of %d bits) is given" % (kbits, nbits))

        p = int(find_p(d0, kbits, e, n,r))
        print("found p: %d" % p)
```
  2.9. EasyBits
- 这题本身的逻辑倒是不难
- 只是分解密文的时候factordb有一个大合数没有分解成功,需要使用yafu本地分解,小跑一段时间即可
- 部分exp
  -
```
    def baseTx(n,base):
    	res = []
    	for i in range(9999):
    		a = n % base
    		b = n//base
    		res.append(a)
    		n = b
    		if n == 0:
    			break
    	return res[::-1]

    def getstr(sq):
    	sq0, sq1 = sq
    	res = []
    	for i in range(len(sq0)):
    		res.append(sq0[i])
    		if i < len(sq1):
    			res.append(sq1[i])
    	if len(sq1) > len(sq0):
    		res.append(sq1[-1])
    	res_bin = ''
    	bin_str = 0
    	for r in res:
    		res_bin += str(bin_str)*r
    		bin_str ^= 1

    	return ''.join([chr(int(res_bin[i:i+8],2)) for i in range(0,len(res_bin),8)])


    c0 = open('ciphertext','rb').read()
    c0 = bytes_to_long(c0)
    from operator import mul
    clist = 
    c = reduce(mul,clist)
    print(c==c0)
    from itertools import combinations,product

    for k in range(1,len(clist)):
    	for sq in combinations(clist,k):
    		n0 = reduce(mul,sq)
    		n1 = c//n0
    		for n0_base,n1_base in product(range(5,8),range(5,8)):
    			sq = [baseTx(n0,n0_base),baseTx(n1,n1_base)]
    			flag = getstr(sq)
    			if checkflag(flag):
    				print('find flag',flag)
```

1. unusual rsa 系列

1.1. unusual rsa 1

1.2. unusual rsa 2

1.3. unusual rsa 3

1.4. unusual rsa 4

1.5. unusual rsa 5

2. 密码挑战系列

2.1. 真·Beginner

2.2. 真·guessguess

2.3. Lousy RSA

2.4. Not That Right Use

2.5. so Damn big e?

2.6. Hammingway

2.7. o

2.8. rsa-rsa-rsa-rsa

2.9. EasyBits

2.7. ^o