Crypto初探

2021-09-01

Crypto

0x01 TryLanguageC

#include <stdio.h>

int main()
{
    int i = 0;
    int numberflag[20] ={567,383,799,775,975,855,383,871,1007,951,1023,991,775,839,1007,887,1023,831,951};
    
    for(i = 0; i<19; i++)
    {
        numberflag[i] = numberflag[i]^ 0x7f;
        numberflag[i] = numberflag[i]>> 3;
        printf("%d ",numberflag[i]);
    }
    printf("\n");
    char flags[20];
    for(i = 0; i<19; i++)
    {
        flags[i] = numberflag[i]; 
        printf("%c",flags[i]);
    }
}

flag:

1	I love cryptography

0x02 Caesar

def decryption():
    #str_list_encry = ['f', 'j', 'y', 'p', 'b', '{', 'e', 'p', "'", 'o', ' ', 'n', 'a', 'w', 'h', 'h', 'u', ' ', 'a', 'v', '}']
    str_list_encry = ['f', 'j', 'y', 'p', 'b', '{', 'e', 'p', "'", 'o', ' ', 'n', 'a', 'a', 'h', 'h', 'u', ' ', 'a', 'v', '}']
    k = 22
    str_list_decry = str_list_encry
    i = 0
    while i < len(str_list_encry):
        if ord(str_list_encry[i]) >= 97 and ord(str_list_encry[i]) <= 122:
            if ord(str_list_encry[i]) >= 97 + k:
                str_list_decry[i] = chr(ord(str_list_encry[i]) - k)
            else:
                str_list_decry[i] = chr(ord(str_list_encry[i]) + 26 - k)
        i = i + 1
    ans = ''
    for i in str_list_decry:
        ans += i
    print(ans)
if __name__ == '__main__':
    decryption()

flag：

1	jnctf{it's reelly ez}

0x03 Affine

将文件下载后更改后缀为.zip得到密文和加密函数

可以通过在线解密或Affine解密脚本得到明文

揭秘脚本：

from Crypto.Util.number import *
msg = 'kwpoyjejccdsjd'

b = inverse(3,26)
print(b)
flag = ''
for i in msg:
    ch = chr(((b*(ord(i)-9-97))) % 26 + 97)
    flag += ch
print(flag)

flag：

1	jnctfahappyday

0x04 EasyRSA

思路

读源码

1 2	p = getPrime(1024) r = getPrime(1024)

说明 r > 1/2 * p 且 r < 2*p

而

while True:
    i += 2
    q = 3 * p + i
    if isprime(q):
        break

说明 q > 3*p

又因为 n = pqr

所以 p^3 < 1/2 * p * 3 * p * p

即 p^3 < 3/2 * p ^ 3 < n

所以 p3 = p^3

而 q3 是否满足 q3 < n 不可证

但知道 q 与 p 的关系即可求 q

知道 p q 密文可解

脚本

from Crypto.Util.number import *
from gmpy2 import *
from sympy import isprime
c = 2640719266133590657730022832895685409886818590742529130791272703737260220305698395550214267009477025083754511134564208388126840197352795391554568852089628652711333028586269115635454638107282121219105579508186870562401540880966200063720371053375341026415095581071187183255698987802885368019870871700857774915233725950970822696385247250265221054710656258324978454404265263686446369080290837987156460143067938467648544634430526204096794262943836014020497700817110841974583666139237514629813147869957856842689681470713605227842055547284336003555723139181600869545764718106325244640576833841807663070278388715784309402394720118620012282693400066270394787635232774022302892979970665474080486912456524934085857681589946874087460165584042497495882954172855474964204705894262448871106724301335314215246535072952084512124152914188674976352450524342669527245135828009232590386075162445795362903690354959715146165796309514709002988718802
e = 65537
n = 9345250986337993905135661253624938224372287590932847460001525089499733443194408248251827273254448424814772103239241741189673809663273467839088175460048985769805223083749548350679299843313706729420743264951740550553770820288610816152984955433836708023721203222275424126365315358299016330836952095356095354096022623502633502246298604405371548255525331664184283254176009041247292848867813881322374703255343797897302512013574426227476914143434791210650434845757739261087192472695850106563494503574222454074522628470873447356096457607883154105847673523681493074326855248386962151192482197219604675188484844871714861633211306931898637098981455274856566215225103391431004216412586297160781567384462887521038343847921062104100156729686463715597041023610681876583898247828951700335614266599238073859923155027126450971899817712150370526303364315562738310131315219185740569803698983202464094954829450125913356611884405478331969336377719
p3 = 2327266026692360322760969674698375370294458376233643545078379431120356953367044147912180257416216275646087769873941422149785277660435326598255331036543494749808645301940714219569817142190079179959543027926984756934145712691289708494795315507936047432703869914022818494155674095290806214371111448325395696090250361500935559865926381637386499120945772846436340842056725596794979641822941418507859160603754200903295825004190310346064126986524501941476690624751438068501947160311800233342861275773106139171834999148557459880455629984646253550035819111983525952508214255738991482641623384556356128988926170930583597581593542357916953130792318920489256603116937454398574116002342328345773124484327302664760642252393678218510632022453955736767142540750713467435792564693894293556583945453422410146466701318350767746744159566092409573991630191651179437153683072005754458163730344401856565927461665000270194023849945430643901214849693

p=iroot(p3,3)[0]
i=0
while True:
    i+=2
    q = 3*p+i
    if isprime(q):
        break

r=n//(p*q)

phi=(p-1)*(q-1)*(r-1)

d=invert(e,phi)  #求模逆  ed ≡ 1 (mod phi)) invert(e,phi)

m=pow(c,d,n)   # m = c^d % n
flag=long_to_bytes(m)
print(flag)

flag

1	jnctf{now_you_know_rsa}

0x05 solve_equations

p和q均形如x^4+a其中x是128位的数，而a是70位的数。

设p=x^4+a，q=y^4+b可得n=p*q=(x*y)^4+a*y^4+b*x^4+a*b

由于a和b过小，如果对n直接开四次方根，可以得到n^(1/4) == x*y

1
2

n = 642490594376281618207440246293358130347533059333546608004801465962276986228377845074254331568169118625276515856878556004934816290475626584329280631731598984725780235581589177352281229458875318652667477178023489539936535622122070992295011875672812842065244674297547830376624928904526157378639668903760372743843
print(iroot(n,4)[0])

解得n_root = 159208662382575641221158086761470934954896410873779789839060715818024475381282

于是可以根据n^(1/4) == x*y以及p=x^4+a，q=y^4+b求解x和y

其中a,b均已知，使用sage求解方程

sage: n_root = 159208662382575641221158086761470934954896410873779789839060715818024475381282
....: r_p,r_q = 1727015030667665707276,2299988782350827510463
....: n = 6424905943762816182074402462933581303475330593335466080048014659622769862283778450742543315681691186252765158568785560049348
....: 16290475626584329280631731598984725780235581589177352281229458875318652667477178023489539936535622122070992295011875672812842065
....: 244674297547830376624928904526157378639668903760372743843
....: var('x,y')
....: eq1 = x*y == n_root
....: eq2 = (x^4+r_p)*(y^4+r_q) == n
....: solve([eq1,eq2],[x,y])
....:
(x, y)
[[x == -159208662382575641221158086761470934954896410873779789839060715818024475381282*sqrt(2/29415241177160086381328602288741943529283565879438137357852640451741461078630669773323994888620129834253335150072218527912253707005108495946469517257432697597483233336390845941)*sqrt(-sqrt(9805080392386695460442867429580647843094521959812712452617546817247153692876889924441331629540043278084445050024072842637417902335036165315489839085810899199161077778796948647)*sqrt(431753757666916426819)), y == sqrt(3/863507515333832853638)*sqrt(-sqrt(9805080392386695460442867429580647843094521959812712452617546817247153692876889924441331629540043278084445050024072842637417902335036165315489839085810899199161077778796948647)*sqrt(431753757666916426819))], [x == -159208662382575641221158086761470934954896410873779789839060715818024475381282*sqrt(2/29415241177160086381328602288741943529283565879438137357852640451741461078630669773323994888620129834253335150072218527912253707005108495946469517257432697597483233336390845941)*sqrt(sqrt(9805080392386695460442867429580647843094521959812712452617546817247153692876889924441331629540043278084445050024072842637417902335036165315489839085810899199161077778796948647)*sqrt(431753757666916426819)), y == -sqrt(3/863507515333832853638)*sqrt(sqrt(9805080392386695460442867429580647843094521959812712452617546817247153692876889924441331629540043278084445050024072842637417902335036165315489839085810899199161077778796948647)*sqrt(431753757666916426819))], [x == 159208662382575641221158086761470934954896410873779789839060715818024475381282*sqrt(2/29415241177160086381328602288741943529283565879438137357852640451741461078630669773323994888620129834253335150072218527912253707005108495946469517257432697597483233336390845941)*sqrt(-sqrt(9805080392386695460442867429580647843094521959812712452617546817247153692876889924441331629540043278084445050024072842637417902335036165315489839085810899199161077778796948647)*sqrt(431753757666916426819)), y == -sqrt(3/863507515333832853638)*sqrt(-sqrt(9805080392386695460442867429580647843094521959812712452617546817247153692876889924441331629540043278084445050024072842637417902335036165315489839085810899199161077778796948647)*sqrt(431753757666916426819))], [x == 159208662382575641221158086761470934954896410873779789839060715818024475381282*sqrt(2/29415241177160086381328602288741943529283565879438137357852640451741461078630669773323994888620129834253335150072218527912253707005108495946469517257432697597483233336390845941)*sqrt(sqrt(9805080392386695460442867429580647843094521959812712452617546817247153692876889924441331629540043278084445050024072842637417902335036165315489839085810899199161077778796948647)*sqrt(431753757666916426819)), y == sqrt(3/863507515333832853638)*sqrt(sqrt(9805080392386695460442867429580647843094521959812712452617546817247153692876889924441331629540043278084445050024072842637417902335036165315489839085810899199161077778796948647)*sqrt(431753757666916426819))], [x == 442580207023874647465714745974078721831, y == 359728383366197966654389101265038571022], [x == -442580207023874647465714745974078721831, y == -359728383366197966654389101265038571022], [x == (442580207023874647465714745974078721831*I), y == (-359728383366197966654389101265038571022*I)], [x == (-442580207023874647465714745974078721831*I), y == (359728383366197966654389101265038571022*I)]]

找出其中整数解：

1 2	x = 442580207023874647465714745974078721831 y = 359728383366197966654389101265038571022

由此可求p、q

from gmpy2 import *
from Crypto.Util.number import *
r_p,r_q = 1727015030667665707276,2299988782350827510463
n = 642490594376281618207440246293358130347533059333546608004801465962276986228377845074254331568169118625276515856878556004934816290475626584329280631731598984725780235581589177352281229458875318652667477178023489539936535622122070992295011875672812842065244674297547830376624928904526157378639668903760372743843
c = 416049882840112103582882397784884075898787749737286099253391410141600634859046652087840140339287449868203444555627058571002713967818793650926678057624685928988989504042741438928290814659188585668588528393789346306012381567356589236431685993106312550345265284603403881430784278137722784079714780863184138303939
x = 442580207023874647465714745974078721831
y = 359728383366197966654389101265038571022
p = x**4+r_p
q = y**4+r_q

phi = (p-1)*(q-1)
e = 0x10001

dd = invert(e,phi)

M = pow(c,dd,n)
flag = M
print(long_to_bytes(flag))

flag:

1	jnctf{b3st_crypt0}