【CTF】BCTF Crypto SpecialRSA writeup

ctf
  1. 1. 题目描述
  • 总结
  • 题目描述

    题目描述

    将附带的zip文件下载并解压。可以看到以下几个文件:

    • 加密算法
    • 示例密文
    • 示例明文
    • 加密的flag文件
      大致我们可以看出来,题目的意图为通过示例密明文,算出加密秘钥k,然后通过k解密flag文件。阅读加解密算法,我们可以得出以下的数学公式:
      1
      2
      3
      4
      5
      gcd(k,N)=1,kd+Ny=1,c=>criphertext,m=>plaintext
      encode c=[(k^r%N)*m]%N
      decode m=[(d^r%N)*c]%N
      已知2组(m,r,c) N 的值
      求解k

    到这里卡了很久,一直没个正确的方式来获取k,不用数学就会忘记啊啊啊啊啊啊啊。后来求组了老师,得到了一个思路。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    下面所有^-1表示对应的乘法逆元
    假设gcd(r1,r2)=1,那么存在a,b使得公式r1*a+r2*b=1
    那么 k^1
    =k^(r1*a+r2*b)
    =k^(r1*a) * k^(r2*b)
    =(k^r1)^a * (k^r2)^b
    而k^rn 可以通过(m,r,c)对来获得
    这里直接使用encode公式c=[(k^r%N)*m]%N
    通过推导可以得出k^r=c*(m^-1)
    m的逆元可以通过扩展欧几里德算法来求得

    有了上面的思路,就可以写程序来加解密了,这里我用了python来写,其中(m,r,c)对我事先拿出来了,清楚一点,下面的程序是来算k的

    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
    import msgpack
    from Crypto.PublicKey import RSA
    N = 23927411014020695772934916764953661641310148480977056645255098192491740356525240675906285700516357578929940114553700976167969964364149615226568689224228028461686617293534115788779955597877965044570493457567420874741357186596425753667455266870402154552439899664446413632716747644854897551940777512522044907132864905644212655387223302410896871080751768224091760934209917984213585513510597619708797688705876805464880105797829380326559399723048092175492203894468752718008631464599810632513162129223356467602508095356584405555329096159917957389834381018137378015593755767450675441331998683799788355179363368220408879117131L

    def Ext_Euclid (a , b ):
    '''
    扩展欧几里得算法 a*x + b*y = gcd(a,b) 返回 x,y以及a,b的最大公约数gcd
    :param a:
    :param b:
    :return:x,y以及a,b的最大公约数gcd

    '''
    if (b == 0):
    return 1 , 0 , a
    else:
    x , y , q=Ext_Euclid( b , a % b )
    x , y = y,( x - (a // b) * y )
    return x , y , q
    m1=8246074182642091125578311828374843698994233243811347691229334829218700728624047916518503687366611595562099039411430662968666847086659721231623198995017758424796091810259884653332576136128144958751327844746991264667007359518181363522934430676655236880489550093852524801304612322373542296281962196795304499711006801211783005857297362930338978872451934860435597545642219213551685973208209873623909629278321181485010964460652298690058747090298312365230671723790850998541956664376820820570709272500330966205578898690396706695024001970727864091436518202414166919020415892764617055978488996164642229582717493375419993187360L

    c1=14548997380897265239778884825381301109965518989661808090688952232381091726761464959572943383024428028270717629953894592890859128818839328499002950828491521254480795364789013196240119403187073307558598496713832435709741997056117831860370227155633169019665564392649528306986826960829410120348913586592199732730933259880469229724149887380005627321752843489564984358708013300524640545437703771424168108213045567568595093421366224818609501318783680497763353618110184078118456368631056649526433730408976988014678391205055298782061128568056163894010397245301425676232126267874656710256838457728944370612289985071385621160886L

    m11=RSA.inverse(m1,N)# 求逆元
    kr1=m11*c1

    m2=15575051453858521753108462063723750986386093067763948316612157946190835527332641201837062951012227815568418309166473080588354562426066694924364886916408150576082667797274000661726279871971377438362829402529682825471299861814829463510659258586020732228351258291527965822977048954720558973840956731377322516168809373640494227129998871167089589689796024458501705704779109152762373660542684880052489213039920383757930855300338529058000330103359636123251274293258L

    c2=12793942795110038319724531875568693507469327176085954164034728727511164833335101755153514030256152878364664079056565385331901196541015393609751624971554016671160730478932343949538202167508319292084519621768851878526657022981883304260886841513342396524869530063372782511380879783246034751883691295368172069170967975561364277514063320691930900258017293871754252209727301719207692321798229276732198521711602080244950295889575423383308099786298184477668302842952215665734671829249323604032320696267130330613134368640401070775927197554082071807605399448960911234829590548855031180158567578928333030631307816223152118126597L

    m21=RSA.inverse(m2,N)
    kr2=m21*c2
    # print kr2

    r1=12900676191620430360427117641859547516838813596331616166760756921115466932766990479475373384324634210232168544745677888398849094363202992662466063289599443L

    r2=7718975159402389617924543100113967512280131630286624078102368166185443466262861344357647019797762407935675150925250503475336639811981984126529557679881059L

    a,b,_=Ext_Euclid(r1,r2)
    print a
    print b
    # print a*r1+b*r2

    x1=RSA.inverse(kr2,N)
    k=(pow(kr1, a,N)*pow(x1,-b,N))%N
    print k

    通过上面的程序可以算出

    k=175971776542095822590595405274258668271271366360140578776612582276966567082080372980811310146217399585938214712928761559525614866113821551467842221588432676885027725038849513527080849158072296957428701767142294778752742980766436072183367444762212399986777124093501619273513421803177347181063254421492621011961L

    接下来就简单了将k带入官方的算法就可以得到flag.BCTF{q0000000000b3333333333-ju57-w0n-pwn20wn!!!!!!!!!!!!}
    上面程序中需要注意的是pow函数不支持指数为负数的情况,所以还要再转一下弯。

    1
    2
    3
    4
    a>0,b<0
    (k^r)^b
    =(k^-r)^-b
    所以可以先求出k^r mod N的逆元

    总结

    数学方面的知识还是短板啊,以后得加强一下:)