首页
社区
课程
招聘
[原创]KCTF2019Q4-南充茶坊-中娅之戒
发表于: 2019-12-9 10:57 5714

[原创]KCTF2019Q4-南充茶坊-中娅之戒

2019-12-9 10:57
5714

作者:中娅之戒

本题目采用规则二,即用户名+序列号。

压缩包中包含两个exe,其中“南充茶坊.exe”是参赛程序,另一个README.txt.exe是彩蛋。

南充茶坊.exe 实际上是一个rar自解压程序,它运行起来后会解压出CM.exe和aplib.dll,放在硬盘里,并运行CM.exe。

CM.exe会利用aplib.dll解压出python可执行程序,放在内存里,并运行。

python可执行程序会构建起python虚拟机,并执行python源代码。


直接解压缩 南充茶坊.exe,可以得到CM.exe和aplib.dll;

CM.exe的最后四字节为0xdeadc0de,将它们删除之后,就可以使用pyinstxtractor成功提取.pyc文件了。


使用某些 pyc反编译工具,即可得到程序源码。

共包含CM.py、CMpub.py、general.py三份代码文件。源码分别如下。

这一组的n有一个因子为p=34508357350889186927005771176009938286558270433215942821530479444470024241863567490529149148811494601012847563892119;

将p+1放到yafu里面可以快速得到:

p+1最大的质因子只有22bit。

在已知p+1的质因子的上界的条件下,n是可以被快速分解的。


我们验证了这个方法,它确实是正确的,也是我们在出题时没有发现的。

我们就此方法进行了讨论,并给出以下命题及其证明:

我们在构造这一组RSA迭代攻击的数据时,仅仅关注了e的阶的大小。

但没有进一步思考它和phi(p-1)、phi(q-1)的关系,及其造成的影响。


对于这样的情形,我们尚未找到其原因,欢迎各位大佬一起来讨论。


Wiener's Attack。

弱点不在于n,而在于私钥d。如果d的比特长度短于n的比特长的四分之一,那么此攻击就会生效。

攻击的过程中可以(顺便)得到n的分解。

算法写对的话,破解时间在1秒以内。

我们发现,网上有些实现此攻击的代码是有缺陷的。使用这些代码时,对于某些情况,即使d很短,也无法攻击成功。

(所以写代码之前还是要记得仔细读论文哦!


这两组RSA的n不互素,将它们做gcd(最大公因数)即可得到质因子。


这一组RSA的n即是(著名的)RSA-768。

曾是RSA破解挑战列表中的一员,后被成功分解,计算时间在两年左右。

现已被列入“RSA黑名单”。

wiki上的RSA-768

(要多多关注安全咨询哦!

((当然了,这种数字在factordb上是一定可以查得到的

(((除了这一组的n之外,其它的n在赛前factordb上都是没有的!


输入某些用户名,有可能会给出一个序列号。将这组用户名和序列号放到主程序里面加密,有惊喜。


iiiiiiiiiiii:一个小肥宅,晚上不睡觉,白天起不来, 

xh1998:国家一级彩蛋制造专家, 

leafpad:仍旧是萌新, 

Venessa:深深觉得还是自然科学有意思的密码学方向在读研(小)究(姑)生(娘), 

}

# 我们的征程是吸尘器和云台

# 两只黄鹂鸣翠柳 一行白鹭上青天

from CMpub import pub_n_list, pub_e_list
from general import valid_serial, valid_username, get_enc_seq, enc0
from Crypto.Util.number import bytes_to_long
from os import system

def check(serial, seq):
    now = serial
    for j in range(len(seq)):
        i = seq[j]
        n = pub_n_list[i]
        e = pub_e_list[i]
        if now > pub_n_list[i]:
            return False
        if i > 0:
            now = pow(now, e, n)
        else:
            now = enc0(now, e, n)
            if 0 == now:
                return False

    return now


def main():
    username0 = input('Please input Username:\t')
    serial0 = input('Please input Serial:\t')
    try:
        valid_serial(serial0)
        valid_username(username0)
    except:
        print('\nInvalid Input\n')
        return
    else:
        serial = int(serial0, 16)
        username = username0.encode('utf-8')
        seq = get_enc_seq(username)
        username = bytes_to_long(username)
        check_value = check(serial, seq)
        if check_value == username:
            print('\nCorrect!\n')
        else:
            print('\nOops! The encrypted Serial is not "' + username0 + '".\n')
        system('pause')


if __name__ == '__main__':
    main()

pub_n_list = [
 1230179032923966355216193664456989083993912178939747632284136330115404600706909248395341278324517175820853286404743710145952644302282044037365125019184623573863075946389644423629304167773956447181872440665027369039751736977631813405,
 1230197346433601576871359147146318345794660644587556813317361121112259736906064757424819981626600536503633922734399282271582600808051530362336101942259823441839299355603967188517947938968081105138847731565260537550727639211683197879,
 1230175103148238074642625667635930176506433011031372989302833308622794392947506662903737049730958209740476679577696669046125817578949235076594181707520951908118478466754559490593457625240572006099913042624607335165510041897534435209,
 1230195419889872144876656964938566328205499234259210834822623032535100815525647028091967713768075507813160118981470260555950945392043292242406398016007295386079663975352275199434079009613722639414793342879897781273997830701207001839,
 1230174827420484335136670743465041112031290639257519417607166302989196920558878232997045073571925815302061150702941267642751824310540753494973942944709182841639107639574372312103384805313053886702823094137071927771880443876497834223,
 1230185988420782350445684618408731075592594374149632568516959143947765502111474165779039038375448460747737995123102271976521803891348006321134167925739699715318653372703575221067707929872597815216923462345784043188962130180912008349,
 1230182067416272799574586563163545941454653137377618375202713428977357995541722463977983142958255155175313052685136009571171283284447072364958073918526788611457558644331357136872625495927467161960356807765452292242153097362794537297,
 1230175667673121302771605367336364266247327534138626737357715728447532125946735363769285915448580252805827932111511713836998047583507066247536863749820566853793525683889378074234787827092004094825431802398656705570322640700888234457,
 1230196215847264556140155304337951587143228841840811940425256504477922246092127337047231112435502675187836322205816125340569108923142351137471846665258392302281836567949024626839375922984390501852966755563575130612920367863203222919,
 1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413]
pub_e_list = [
 516522834974778788822737622050071002228140433403308439492366176194856535110473049678585760137133115927927751389873437178270126066640141239601219481836725664034890696476089482771855782560150644578106217444113872365843767702019835165,
 763019398230639020385095590111745749325105506404934257293148841704076883985487416392986296273940405033341623636375465706381388882972769884442281412068657916633528090146878551371406807944205178239005601520958614234641039656871416589,
 758988267473789691400810521950661631157749425185051374867090671651749645717430551141709267885532654476900928589359256799354189000242807872593092025777838259738748452497031844208902096380110211365512236965688511597330444132995706089,
 1160624249765899561934599801255171381291816170997589163041066264243942985094428544791715385847964978883555709070528078257993944356365754193784103706700609561770247555832359683008614876192584738534198649251915489100192910235497240729,
 969584864618350548573879514405798110739020997255786147754353418263140741786718203172013471748696400657712445258494301947449205093259143099235572291402265831321039275001497928579686310419303799571460516007736804962510266314260484877,
 977635869919691501956476862485989771461480520535754082824505449124021204549179419508424215127475063873127952064971338143136691515421466871627243381628988777601672460858098249144471775030169367579800220246847826510445608881346258241,
 78547544255936347746865903259860321812178052069796003154571672431430356709336862994676369608681727972743046653319757142976388460246409300441314120923213061705641045744824531268088986356203751782848608006264879618324460588039470689,
 917852167599983949701460374746950168138446186550074700858636881546192542929330983597633909534315139846805451671216776221152853388795036676315895948093016056124384137235869660229554239964598066970045657946753074761366723500887474273,
 512767915836808239407587704603826045022417741229198687031456060058182528147222248648359114235863620155721720617193551963387219761946115199232261616095015003006138489919312964841684835736418589367746436759162173805823822810793395319,
 1528664914065178933673821962753205462549978186396819666317790993639228285768444490202530533489915241541000489357324333513953018274712260336841857865516134868397620862505815431605074038377372062941322744934135683316080403207986149067]

pub_n_list = [
 1230179032923966355216193664456989083993912178939747632284136330115404600706909248395341278324517175820853286404743710145952644302282044037365125019184623573863075946389644423629304167773956447181872440665027369039751736977631813405,
 1230197346433601576871359147146318345794660644587556813317361121112259736906064757424819981626600536503633922734399282271582600808051530362336101942259823441839299355603967188517947938968081105138847731565260537550727639211683197879,
 1230175103148238074642625667635930176506433011031372989302833308622794392947506662903737049730958209740476679577696669046125817578949235076594181707520951908118478466754559490593457625240572006099913042624607335165510041897534435209,
 1230195419889872144876656964938566328205499234259210834822623032535100815525647028091967713768075507813160118981470260555950945392043292242406398016007295386079663975352275199434079009613722639414793342879897781273997830701207001839,
 1230174827420484335136670743465041112031290639257519417607166302989196920558878232997045073571925815302061150702941267642751824310540753494973942944709182841639107639574372312103384805313053886702823094137071927771880443876497834223,
 1230185988420782350445684618408731075592594374149632568516959143947765502111474165779039038375448460747737995123102271976521803891348006321134167925739699715318653372703575221067707929872597815216923462345784043188962130180912008349,
 1230182067416272799574586563163545941454653137377618375202713428977357995541722463977983142958255155175313052685136009571171283284447072364958073918526788611457558644331357136872625495927467161960356807765452292242153097362794537297,
 1230175667673121302771605367336364266247327534138626737357715728447532125946735363769285915448580252805827932111511713836998047583507066247536863749820566853793525683889378074234787827092004094825431802398656705570322640700888234457,
 1230196215847264556140155304337951587143228841840811940425256504477922246092127337047231112435502675187836322205816125340569108923142351137471846665258392302281836567949024626839375922984390501852966755563575130612920367863203222919,
 1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413]
pub_e_list = [
 516522834974778788822737622050071002228140433403308439492366176194856535110473049678585760137133115927927751389873437178270126066640141239601219481836725664034890696476089482771855782560150644578106217444113872365843767702019835165,
 763019398230639020385095590111745749325105506404934257293148841704076883985487416392986296273940405033341623636375465706381388882972769884442281412068657916633528090146878551371406807944205178239005601520958614234641039656871416589,
 758988267473789691400810521950661631157749425185051374867090671651749645717430551141709267885532654476900928589359256799354189000242807872593092025777838259738748452497031844208902096380110211365512236965688511597330444132995706089,
 1160624249765899561934599801255171381291816170997589163041066264243942985094428544791715385847964978883555709070528078257993944356365754193784103706700609561770247555832359683008614876192584738534198649251915489100192910235497240729,
 969584864618350548573879514405798110739020997255786147754353418263140741786718203172013471748696400657712445258494301947449205093259143099235572291402265831321039275001497928579686310419303799571460516007736804962510266314260484877,
 977635869919691501956476862485989771461480520535754082824505449124021204549179419508424215127475063873127952064971338143136691515421466871627243381628988777601672460858098249144471775030169367579800220246847826510445608881346258241,
 78547544255936347746865903259860321812178052069796003154571672431430356709336862994676369608681727972743046653319757142976388460246409300441314120923213061705641045744824531268088986356203751782848608006264879618324460588039470689,
 917852167599983949701460374746950168138446186550074700858636881546192542929330983597633909534315139846805451671216776221152853388795036676315895948093016056124384137235869660229554239964598066970045657946753074761366723500887474273,
 512767915836808239407587704603826045022417741229198687031456060058182528147222248648359114235863620155721720617193551963387219761946115199232261616095015003006138489919312964841684835736418589367746436759162173805823822810793395319,
 1528664914065178933673821962753205462549978186396819666317790993639228285768444490202530533489915241541000489357324333513953018274712260336841857865516134868397620862505815431605074038377372062941322744934135683316080403207986149067]

from hashlib import sha256

def valid_serial(serial):
    assert type(serial) == str
    assert len(serial) > 0
    if not '0' != serial[0]:
        assert 1 == len(serial)
        for c in serial:
            if not ord('0') <= ord(c) <= ord('9'):
                if not ord('A') <= ord(c) <= ord('F'):
                    raise AssertionError

        return serial


def valid_username(username):
    assert type(username) == str
    assert len(username) > 0
    for c in username:
        assert ord(c) > 0

    return username


def get_enc_seq(username):
    h = sha256()
    h.update(username)
    hash_value = int(h.hexdigest(), 16)
    T = 9
    S = 10
    stat = [0] * (T + 1)
    seq = [0]
    n = hash_value
    while n > 0:
        if S * T > len(seq):
            now = n % T + 1
            if stat[now] < S:
                seq.append(now)
                stat[now] += 1
            n //= T

    return seq


def enc0(m, e, n):
    nbit = 192
    T = (n.bit_length() - 1) // nbit + 1
    ans = 0
    for i in range(T - 1, -1, -1):

        def xxx(x, t):
            return x >> t * nbit & (1 << nbit) - 1

        now_n = xxx(n, i)
        now_e = xxx(e, i)
        now_m = xxx(m, i)
        if now_m >= now_n:
            return 0
        ans = (ans << nbit) + pow(now_m, now_e, now_n)

    return ans

from hashlib import sha256

def valid_serial(serial):
    assert type(serial) == str
    assert len(serial) > 0
    if not '0' != serial[0]:
        assert 1 == len(serial)
        for c in serial:
            if not ord('0') <= ord(c) <= ord('9'):
                if not ord('A') <= ord(c) <= ord('F'):
                    raise AssertionError

        return serial


def valid_username(username):
    assert type(username) == str
    assert len(username) > 0
    for c in username:
        assert ord(c) > 0

    return username


def get_enc_seq(username):
    h = sha256()
    h.update(username)
    hash_value = int(h.hexdigest(), 16)
    T = 9
    S = 10
    stat = [0] * (T + 1)
    seq = [0]
    n = hash_value
    while n > 0:
        if S * T > len(seq):
            now = n % T + 1
            if stat[now] < S:
                seq.append(now)
                stat[now] += 1
            n //= T

    return seq


def enc0(m, e, n):
    nbit = 192
    T = (n.bit_length() - 1) // nbit + 1
    ans = 0
    for i in range(T - 1, -1, -1):

        def xxx(x, t):
            return x >> t * nbit & (1 << nbit) - 1

        now_n = xxx(n, i)
        now_e = xxx(e, i)
        now_m = xxx(m, i)
        if now_m >= now_n:
            return 0
        ans = (ans << nbit) + pow(now_m, now_e, now_n)

    return ans

三份python代码中,CMpub.py的结构最简单,放了10组n、e。
general.py中只有一些函数,供CM.py调用。
主程序CM.py的执行流程如下:
  1. 对输入的用户名和序列号进行了合规性检查。
  2. 调用get_enc_seq函数,借用SHA256,将输入的用户名转换为一个由0到9组成的列表。
  3. 利用该列表对序列号进行加密;该列表即为加密序列,0到9中的每一个数对应一组n、e;除第0组的加密方式较为特殊以外,其它均为常规的RSA加密。
  4. 经过一系列的加密之后,将序列号的加密结果与用户名作比较,相等即正确。
因此,只要能破解这十组RSA加密,此题即可攻破。

第0组实际上包含有4个192bit的RSA;第1-9组均为768bit的RSA。

对于RSA算法,如果能够将公钥的n分解,那么就可以将其攻破。
对于大整数分解,常用的工具有yafumsieve等;factordb可以查到一些已被分解的大整数的结果。

当然,破解一个RSA并不一定完全依赖于直接分解一个大整数。

[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入!

最后于 2019-12-12 00:12 被iiiiiiiiiiii编辑 ,原因:
上传的附件:
收藏
免费 4
支持
分享
最新回复 (5)
雪    币: 11705
活跃值: (975)
能力值: ( LV12,RANK:779 )
在线值:
发帖
回帖
粉丝
2

关于 第5组, 一开始我测试的方法是:

Xi+1 = powmod(Xi, e, n)

依次用第i项与第0项做差, gcd(Xi - X0, N) = p , 结果发现一次就成功了。 即 gcd(x1-x0, n) = p

发现e应该和 phi(phi(n))有联系才这样。

不过我感兴趣的是, 作者是怎样用p,q生成这个e的?
2019-12-9 16:47
1
雪    币: 1048
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
3
过于高端
2019-12-9 17:08
0
雪    币: 1500
活跃值: (319)
能力值: ( LV6,RANK:92 )
在线值:
发帖
回帖
粉丝
4
1、取一个和phi(phi(N))互质的数a,a可能是生成元也可能不是;
2、取一个phi(phi(N))的因数t,目前它是最后e的阶的一个整数倍,即 e的阶 | 现在的t值;
3、计算T=phi(phi(N)) / t;
4、取e=a^T mod phi(N),必然有e^t=1 mod phi(N);
5、若存在t的一个质因子s,使得e^(t/s)=1 mod phi(N),则赋值t:=t/s;
6、重复第5步直到确认当前t值为e的阶。
最后于 2019-12-9 20:42 被iiiiiiiiiiii编辑 ,原因:
2019-12-9 20:41
0
雪    币: 13075
活跃值: (5733)
能力值: ( LV5,RANK:77 )
在线值:
发帖
回帖
粉丝
qux
5
有没有可能写一个彩蛋的解析文章呢?感觉彩蛋也挺有意思的
2019-12-13 00:36
0
雪    币: 10845
活跃值: (1054)
能力值: (RANK:190 )
在线值:
发帖
回帖
粉丝
6
qux 有没有可能写一个彩蛋的解析文章呢?感觉彩蛋也挺有意思的
彩蛋是留给大家慢慢玩的
比赛尚未结束,有大佬说最近忙
所以我们先等等吧
如果大家玩得差不多了,我们就公开彩蛋

彩蛋中有迷宫哟
2019-12-13 14:40
0
游客
登录 | 注册 方可回帖
返回
//