[TOC]

# Tóm lược về RSA
## Thuật toán

RSA là thuật toán mã hóa công khai cho nên sẽ gồm có 2 cặp khóa công khai và khóa bí mật. Các khóa công khai có dạng $\displaystyle ( n,e)$ được khởi tạo như sau:

- Ta chọn $\displaystyle n=pq$ là tích của hai số nguyên tố lớn $\displaystyle p$ và $\displaystyle q$
- Số mũ lập mã của ta sẽ là số nguyên dương $\displaystyle e$ thỏa mãn $\displaystyle \gcd( e,( p-1)( q-1)) =1$.

Tiếp theo là cặp khóa bí mật $\displaystyle ( n,d)$:

- $\displaystyle d$ là số nguyên dương thỏa mãn $\displaystyle ed\equiv 1(\bmod( p-1)( q-1))$
- $\displaystyle n$ là số ban đầu mà ta chọn

Bây giờ, nếu hai người Alice và Bob muốn truyền tin cho nhau thì đầu tiên Alice sẽ tính toán các khóa công khai $\displaystyle ( n,e)$ và gửi cho Bob (khóa được công khai và ai cũng có thể sử dụng được). Sau đó Bob sẽ xử lí plaintext mà mình muốn gửi, chuyển nó về một số nguyên dương $\displaystyle m< n$. Nếu tin nhắn quá dài và $\displaystyle m >n$ thì có thể chia nhỏ ra để xử lí từng phần.

Tiếp theo Bob sẽ tính $\displaystyle c=m^{e}\bmod n$ là ciphertext được mã hóa bằng cặp khóa công khai $\displaystyle ( n,e)$ và gửi cho Alice. Alice nhận được $\displaystyle c$ và sẽ sử dụng cặp khóa bí mật của mình để giải mã. Cụ thể

\begin{equation*}
c^{d} \equiv \left( m^{e}\right)^{d} \equiv m\bmod n
\end{equation*}

Do $\displaystyle m< n$ nên $\displaystyle m\bmod n=m$. Như vậy nếu tìm được khóa $d$ thì ta có thể bẻ khóa được hệ mật RSA.

Người ta cũng chứng minh được rằng độ khó của bài toán tìm khóa bí mật $d$ dựa vào cặp khóa công khai tương đương với bài toán phân tích thừa số nguyên tố của $n$.

## Về mặt toán học

Về cơ bản thuật toán mã hóa RSA hoạt động dựa trên tính chất của phi hàm Euler và định lí Euler. Cụ thể như sau:

**Định nghĩa 1.** Cho $\displaystyle n\geqslant 1$ là một số nguyên dương. Số các số nguyên dương không vượt quá $\displaystyle n$ và nguyên tố cùng nhau với $\displaystyle n$ chính là $\displaystyle \varphi ( n)$ hay còn gọi là phi hàm Euler của $\displaystyle n$.

**Định nghĩa 2.** Tập hợp các số nguyên $\displaystyle A=\{a_{1} ,a_{2} ,...,a_{n}\}$ được gọi là hệ thặng dư đầy đủ modulo $\displaystyle n$ khi và chỉ khi hai số bất kì trong tập hợp không đồng dư với nhau theo modulo $\displaystyle n$. Nói cách khác tập số dư $\displaystyle r_{i}$ của $\displaystyle a_{i}$ khi chia cho $\displaystyle n$ sẽ trùng với tập $\displaystyle \{0,1,...,n-1\}$.

**Định nghĩa 3.** Tập hợp các số nguyên $\displaystyle B=\{b_{1} ,...,b_{\varphi ( n)}\}$ được gọi là hệ thặng dư thu gọn modulo $\displaystyle n$ khi và chỉ khi $\displaystyle ( b_{i} ,n) =1,\forall i=1,...,\varphi ( n)$ và $\displaystyle b_{i}\not{\equiv } b_{j}(\bmod n) ,\forall i,j$.

Từ các định nghĩa trên ta sẽ đi chứng minh định lí Euler như sau:

**Định lí Euler.** Cho $\displaystyle a,m$ là các số nguyên dương và $\displaystyle \gcd( a,m) =1$. Khi đó
\begin{equation*}
a^{\varphi ( m)} \equiv 1(\bmod m)
\end{equation*}

Chứng minh.

Gọi $\displaystyle M=\{m_{1} ,...,m_{\varphi ( m)}\}$ là hệ thặng dư thu gọn modulo $\displaystyle m$. Khi đó với $\displaystyle ( a,m) =1$ thì ta cũng có $\displaystyle aM$ là hệ thặng dư thu gọn modulo $\displaystyle m$. Thật vậy, xét $\displaystyle am_{i} ,am_{j} \in aM$ và giả sử $\displaystyle am_{i} \equiv am_{j}\bmod m$ thì khi đó
\begin{gather*}
a( m_{i} -m_{j}) \equiv 0\bmod m\\
\leftrightarrow m_{i} \equiv m_{j}\bmod m
\end{gather*}

là điều vô lí vì $\displaystyle m_{i} \neq m_{j}$. Lấy tích lần lượt các phần tử của hai tập thì ta có
\begin{gather*}
am_{1} am_{2} ...am_{\varphi ( m)} \equiv m_{1} m_{2} ...m_{\varphi ( m)}\bmod m\\
\leftrightarrow a^{\varphi ( m)} \equiv 1(\bmod m)
\end{gather*}

Vậy ta có điều phải chứng mimh.

Cách tính cụ thể cho phi hàm Euler thì mọi người tham khảo ở [Wikipedia](https://vi.wikipedia.org/wiki/H%C3%A0m_phi_Euler) hoặc trong phần tài liệu tham khảo.

Như vậy ta thấy, để tính được $d$ thì ta phải tính được $\varphi(n)$, nhưng để tính được $\varphi(n)$ thì ta phải phân tích được $n$.

Ta để ý thêm rằng $\displaystyle m^{ed} \equiv m^{1+k\varphi ( n)} \equiv m\cdot \left( m^{k}\right)^{\varphi ( n)} \equiv m\bmod n$ tức là ta có $\displaystyle \left( m^{k}\right)^{\varphi ( n)} \equiv 1(\bmod n)$? Điều này không hẳn đúng vì ta không chắc $\displaystyle ( m,n) =1$ hay không. Nếu như $\displaystyle ( m,n) \neq 1$ thì đẳng thức $\displaystyle \left( m^{k}\right)^{\varphi ( n)} \equiv 1(\bmod n)$ là sai. Vậy làm sao ta đảm bảo được rằng trong quá trình truyền dữ liệu, số $\displaystyle m$ mà ta chọn luôn thỏa $\displaystyle ( m,n) =1$ (nếu tính toán lại thì sẽ rất lâu).

Mình có đọc được bài viết này trên [Crypto StackExchange](https://crypto.stackexchange.com/questions/25648/how-do-we-guarantee-plaintext-is-coprime-in-rsa)

Tác giả bài viết chỉ ra rằng xác suất để "bốc trúng" một số nhỏ hơn $n$ mà không nguyên tố cùng nhau với nó là rất thấp. Cụ thể với $n=pq$ thì xác suất sẽ là $\displaystyle \frac{p+q-1}{pq} < \frac{p+q}{pq} =\frac{1}{p} +\frac{1}{q} \ \sim 0$, gần như không thể xảy ra với $p,q$ là các số nguyên tố rất lớn.

# Starter

## Modular Exponentiation
Dùng hàm `pow` trong `pycryptodome`

from Cryptodome.Util.number import *
print(pow(101,17,22663))

## Public Keys

from Cryptodome.Util.number import *
pt=12
e=65537
p=17
q=23
n=p*q
print(pow(pt,e,n))

## Euler's Totient
Để bài yêu cầu tính phi hàm Euler của số $n$.

from Cryptodome.Util.number import *
p= 857504083339712752489993810777
q= 1029224947942998075080348647219
print((p-1)*(q-1))

P/s: một số thuật tính phi hàm Euler của $n$ cho trước:

def sieve(limit):
    A=[True for _ in range(limit+1)]
    A[0]=A[1]=False
    p=2 
    while (p*p<=limit):
        if A[p]==True:
            for j in range(p*p,limit+1,p):
                A[j]=False
        p+=1
    prime=[]
    for p in range (2,limit+1):
        if A[p]==True: 
            prime.append(p)
    return prime
def prime_fac_sieve(n):
    factors={}
    prime=sieve(n//2)
    for p in prime: 
        if p * p >= n:
            break
        while n % p == 0:
            if p in factors:
                factors[p] +=1
            else:
                factors[p]=1
            n//=p
    if n > 1 :
        factors[n]=1
    return factors



def euler_totient(n):
    prime_factors=prime_fac_sieve(n)
    result=1
    for p,exp in prime_factors.items():
        result *= (p**(exp)-p**(exp-1))
    return result


def faster_phi(n):
    res=n
    i=2
    while i * i <= n: # vì các ước nguyên tố 
        #của n nếu có ước lớn nhất thì cũng không thể vượt quá n / 2 trừ khi n chính là một số nguyên tố. 
        if n % i == 0 :
            while n % i == 0:
                n//=i
            res-=res//i
        i += 1 
    if n > 1:
        res-=res//n # xử lí trường hợp n là số nguyên tố, hoặc n có ước nguyên tố lớn hơn căn n 
    return res

## Private Keys
Tính khóa bí mật $d$ trong mã hóa RSA từ các khóa công khai:

from Cryptodome.Util.number import *
e = 65537
p = 857504083339712752489993810777
q = 1029224947942998075080348647219
phi=((p-1)*(q-1))
d=inverse(e,phi)
print(d)

## RSA Decryption
Bài cho cặp khóa công khai $(N,e)$. Có thể dùng Sage để factor:


from Cryptodome.Util.number import *
n=882564595536224140639625987659416029426239230804614613279163
e=65537
p=857504083339712752489993810777
q=1029224947942998075080348647219
phi=(p-1)*(q-1)
d=inverse(e,phi)
ct=77578995801157823671636298847186723593814843845525223303932
pt=pow(ct,d,n)
print(pt)

## RSA Signatures

Chall cho ta cặp khóa bí mật:

N = 15216583654836731327639981224133918855895948374072384050848479908982286890731769486609085918857664046075375253168955058743185664390273058074450390236774324903305663479046566232967297765731625328029814055635316002591227570271271445226094919864475407884459980489638001092788574811554149774028950310695112688723853763743238753349782508121985338746755237819373178699343135091783992299561827389745132880022259873387524273298850340648779897909381979714026837172003953221052431217940632552930880000919436507245150726543040714721553361063311954285289857582079880295199632757829525723874753306371990452491305564061051059885803
d = 11175901210643014262548222473449533091378848269490518850474399681690547281665059317155831692300453197335735728459259392366823302405685389586883670043744683993709123180805154631088513521456979317628012721881537154107239389466063136007337120599915456659758559300673444689263854921332185562706707573660658164991098457874495054854491474065039621922972671588299315846306069845169959451250821044417886630346229021305410340100401530146135418806544340908355106582089082980533651095594192031411679866134256418292249592135441145384466261279428795408721990564658703903787956958168449841491667690491585550160457893350536334242689

Và dùng cặp khóa này để kí văn bản


Code:

from Cryptodome.Util.number import *
from hashlib import sha256
n = 15216583654836731327639981224133918855895948374072384050848479908982286890731769486609085918857664046075375253168955058743185664390273058074450390236774324903305663479046566232967297765731625328029814055635316002591227570271271445226094919864475407884459980489638001092788574811554149774028950310695112688723853763743238753349782508121985338746755237819373178699343135091783992299561827389745132880022259873387524273298850340648779897909381979714026837172003953221052431217940632552930880000919436507245150726543040714721553361063311954285289857582079880295199632757829525723874753306371990452491305564061051059885803
d = 11175901210643014262548222473449533091378848269490518850474399681690547281665059317155831692300453197335735728459259392366823302405685389586883670043744683993709123180805154631088513521456979317628012721881537154107239389466063136007337120599915456659758559300673444689263854921332185562706707573660658164991098457874495054854491474065039621922972671588299315846306069845169959451250821044417886630346229021305410340100401530146135418806544340908355106582089082980533651095594192031411679866134256418292249592135441145384466261279428795408721990564658703903787956958168449841491667690491585550160457893350536334242689
msg=b'crypto{Immut4ble_m3ssag1ng}'
msg=sha256(msg).hexdigest()
msg_bytes=bytes.fromhex(msg)
m=pow(bytes_to_long(msg_bytes),d,n)
print(m)

# Primes Part 1

## Factoring
Bài yêu cầu ta phân tích thừa số nguyên tố. Ta có thể sử dụng FactorDB

## Inferius Prime
Source code của bài:

#!/usr/bin/env python3

from Crypto.Util.number import getPrime, inverse, bytes_to_long, long_to_bytes, GCD

e = 0x10001

# n will be 8 * (100 + 100) = 1600 bits strong (I think?) which is pretty good
p = getPrime(100)
q = getPrime(100)
phi = (p - 1) * (q - 1)
d = inverse(e, phi)

n = p * q

FLAG = b"crypto{???????????????}"
pt = bytes_to_long(FLAG)
ct = pow(pt, e, n)

print(f"n = {n}")
print(f"e = {e}")
print(f"ct = {ct}")

pt = pow(ct, d, n)
decrypted = long_to_bytes(pt)
assert decrypted == FLAG

và file output.txt

n = 984994081290620368062168960884976209711107645166770780785733
e = 65537
ct = 948553474947320504624302879933619818331484350431616834086273

$n$ của bài này khá nhỏ nên ta có thể dùng hàm `factor` của `sagemath` để phân tích.

from Cryptodome.Util.number import *
from sage.all import *
e=65537
ct=948553474947320504624302879933619818331484350431616834086273
n=984994081290620368062168960884976209711107645166770780785733
factors=factor(n)
p,q=factors[0][0],factors[1][0]
phi=(p-1)*(q-1)

d=inverse(e,phi)
result=(pow(ct,d,n))
print(long_to_bytes(result))

## Monoprime
output.txt

n = 171731371218065444125482536302245915415603318380280392385291836472299752747934607246477508507827284075763910264995326010251268493630501989810855418416643352631102434317900028697993224868629935657273062472544675693365930943308086634291936846505861203914449338007760990051788980485462592823446469606824421932591                                                                  
e = 65537
ct = 161367550346730604451454756189028938964941280347662098798775466019463375610700074840105776873791605070092554650190486030367121011578171525759600774739890458414593857709994072516290998135846956596662071379067305011746842247628316996977338024343628757374524136260758515864509435302781735938531030576289086798942  

$n$ ở bài này chính là một số nguyên tố

from Cryptodome.Util.number import *
from sage.all import *
e=65537
ct=161367550346730604451454756189028938964941280347662098798775466019463375610700074840105776873791605070092554650190486030367121011578171525759600774739890458414593857709994072516290998135846956596662071379067305011746842247628316996977338024343628757374524136260758515864509435302781735938531030576289086798942
n=171731371218065444125482536302245915415603318380280392385291836472299752747934607246477508507827284075763910264995326010251268493630501989810855418416643352631102434317900028697993224868629935657273062472544675693365930943308086634291936846505861203914449338007760990051788980485462592823446469606824421932591
phi=n-1
d=inverse(e,phi)
result=(pow(ct,d,n))
print(long_to_bytes(result))

## Square Eyes
Bài này cho ta một file output.txt
Từ đề bài ta biết được gợi ý $n$ là một số chính phương. Dùng FactorDB thì lấy được $p$ thỏa $p^{2}=n$.

n = 535860808044009550029177135708168016201451343147313565371014459027743491739422885443084705720731409713775527993719682583669164873806842043288439828071789970694759080842162253955259590552283047728782812946845160334801782088068154453021936721710269050985805054692096738777321796153384024897615594493453068138341203673749514094546000253631902991617197847584519694152122765406982133526594928685232381934742152195861380221224370858128736975959176861651044370378539093990198336298572944512738570839396588590096813217791191895941380464803377602779240663133834952329316862399581950590588006371221334128215409197603236942597674756728212232134056562716399155080108881105952768189193728827484667349378091100068224404684701674782399200373192433062767622841264055426035349769018117299620554803902490432339600566432246795818167460916180647394169157647245603555692735630862148715428791242764799469896924753470539857080767170052783918273180304835318388177089674231640910337743789750979216202573226794240332797892868276309400253925932223895530714169648116569013581643192341931800785254715083294526325980247219218364118877864892068185905587410977152737936310734712276956663192182487672474651103240004173381041237906849437490609652395748868434296753449
e = 65537
ct = 222502885974182429500948389840563415291534726891354573907329512556439632810921927905220486727807436668035929302442754225952786602492250448020341217733646472982286222338860566076161977786095675944552232391481278782019346283900959677167026636830252067048759720251671811058647569724495547940966885025629807079171218371644528053562232396674283745310132242492367274184667845174514466834132589971388067076980563188513333661165819462428837210575342101036356974189393390097403614434491507672459254969638032776897417674577487775755539964915035731988499983726435005007850876000232292458554577437739427313453671492956668188219600633325930981748162455965093222648173134777571527681591366164711307355510889316052064146089646772869610726671696699221157985834325663661400034831442431209123478778078255846830522226390964119818784903330200488705212765569163495571851459355520398928214206285080883954881888668509262455490889283862560453598662919522224935145694435885396500780651530829377030371611921181207362217397805303962112100190783763061909945889717878397740711340114311597934724670601992737526668932871436226135393872881664511222789565256059138002651403875484920711316522536260604255269532161594824301047729082877262812899724246757871448545439896

from Cryptodome.Util.number import *

n = ...
e = 65537
ct = 222502885974182429500948389840563415291534726891354573907329512556439632810921927905220486727807436668035929302442754225952786602492250448020341217733646472982286222338860566076161977786095675944552232391481278782019346283900959677167026636830252067048759720251671811058647569724495547940966885025629807079171218371644528053562232396674283745310132242492367274184667845174514466834132589971388067076980563188513333661165819462428837210575342101036356974189393390097403614434491507672459254969638032776897417674577487775755539964915035731988499983726435005007850876000232292458554577437739427313453671492956668188219600633325930981748162455965093222648173134777571527681591366164711307355510889316052064146089646772869610726671696699221157985834325663661400034831442431209123478778078255846830522226390964119818784903330200488705212765569163495571851459355520398928214206285080883954881888668509262455490889283862560453598662919522224935145694435885396500780651530829377030371611921181207362217397805303962112100190783763061909945889717878397740711340114311597934724670601992737526668932871436226135393872881664511222789565256059138002651403875484920711316522536260604255269532161594824301047729082877262812899724246757871448545439896

p = q = 23148667521998097720857168827790771337662483716348435477360567409355026169165934446949809664595523770853897203103759106983985113264049057416908191166720008503275951625738975666019029172377653170602440373579593292576530667773951407647222757756437867216095193174201323278896027294517792607881861855264600525772460745259440301156930943255240915685718552334192230264780355799179037816026330705422484000086542362084006958158550346395941862383925942033730030004606360308379776255436206440529441711859246811586652746028418496020145441513037535475380962562108920699929022900677901988508936509354385660735694568216631382653107

phi = (p-1)*(q)
d = inverse(e,phi)

decrypt = pow(ct,d,n)
print(long_to_bytes(decrypt))

## Manyprime
output.txt

n = 171731371218065444125482536302245915415603318380280392385291836472299752747934607246477508507827284075763910264995326010251268493630501989810855418416643352631102434317900028697993224868629935657273062472544675693365930943308086634291936846505861203914449338007760990051788980485462592823446469606824421932591                                                                  
e = 65537
ct = 161367550346730604451454756189028938964941280347662098798775466019463375610700074840105776873791605070092554650190486030367121011578171525759600774739890458414593857709994072516290998135846956596662071379067305011746842247628316996977338024343628757374524136260758515864509435302781735938531030576289086798942  

Bài này thì $n$ là tích của nhiều số nguyên tố nhỏ nên ta sẽ dùng `sage` để phân tích.

from Cryptodome.Util.number import *
from sage.all import *
n = 580642391898843192929563856870897799650883152718761762932292482252152591279871421569162037190419036435041797739880389529593674485555792234900969402019055601781662044515999210032698275981631376651117318677368742867687180140048715627160641771118040372573575479330830092989800730105573700557717146251860588802509310534792310748898504394966263819959963273509119791037525504422606634640173277598774814099540555569257179715908642917355365791447508751401889724095964924513196281345665480688029639999472649549163147599540142367575413885729653166517595719991872223011969856259344396899748662101941230745601719730556631637
e = 65537
ct = 320721490534624434149993723527322977960556510750628354856260732098109692581338409999983376131354918370047625150454728718467998870322344980985635149656977787964380651868131740312053755501594999166365821315043312308622388016666802478485476059625888033017198083472976011719998333985531756978678758897472845358167730221506573817798467100023754709109274265835201757369829744113233607359526441007577850111228850004361838028842815813724076511058179239339760639518034583306154826603816927757236549096339501503316601078891287408682099750164720032975016814187899399273719181407940397071512493967454225665490162619270814464
def euler_totient(n):
    result=1
    factors=factor(n)
    for prime, exponent in factors:
        result*=prime**(exponent-1)*(prime-1)
    return result
phi=euler_totient(n)
d=inverse(e,phi)
decrypt = pow(ct,d,n)
print(long_to_bytes(decrypt))

# Public exponent
## Salty
Soucre code của bài:

#!/usr/bin/env python3

from Crypto.Util.number import getPrime, inverse, bytes_to_long, long_to_bytes

e = 1
d = -1

while d == -1:
    p = getPrime(512)
    q = getPrime(512)
    phi = (p - 1) * (q - 1)
    d = inverse(e, phi)

n = p * q

flag = b"XXXXXXXXXXXXXXXXXXXXXXX"
pt = bytes_to_long(flag)
ct = pow(pt, e, n)

print(f"n = {n}")
print(f"e = {e}")
print(f"ct = {ct}")

pt = pow(ct, d, n)
decrypted = long_to_bytes(pt)
assert decrypted == flag

Và file ouput.txt

n = 110581795715958566206600392161360212579669637391437097703685154237017351570464767725324182051199901920318211290404777259728923614917211291562555864753005179326101890427669819834642007924406862482343614488768256951616086287044725034412802176312273081322195866046098595306261781788276570920467840172004530873767                                                                  
e = 1
ct = 44981230718212183604274785925793145442655465025264554046028251311164494127485

Do bài này $e=1$ nên $d=1$ luôn.

from Cryptodome.Util.number import *
ct = 44981230718212183604274785925793145442655465025264554046028251311164494127485
print(long_to_bytes(ct).decode())

`crypto{saltstack_fell_for_this!}`
## Modulus Inutilis
Source code của bài:

#!/usr/bin/env python3

from Crypto.Util.number import getPrime, inverse, bytes_to_long, long_to_bytes

e = 3
d = -1

while d == -1:
    p = getPrime(1024)
    q = getPrime(1024)
    phi = (p - 1) * (q - 1)
    d = inverse(e, phi)

n = p * q

flag = b"XXXXXXXXXXXXXXXXXXXXXXX"
pt = bytes_to_long(flag)
ct = pow(pt, e, n)

print(f"n = {n}")
print(f"e = {e}")
print(f"ct = {ct}")

pt = pow(ct, d, n)
decrypted = long_to_bytes(pt)
assert decrypted == flag

Output.txt

n = 17258212916191948536348548470938004244269544560039009244721959293554822498047075403658429865201816363311805874117705688359853941515579440852166618074161313773416434156467811969628473425365608002907061241714688204565170146117869742910273064909154666642642308154422770994836108669814632309362483307560217924183202838588431342622551598499747369771295105890359290073146330677383341121242366368309126850094371525078749496850520075015636716490087482193603562501577348571256210991732071282478547626856068209192987351212490642903450263288650415552403935705444809043563866466823492258216747445926536608548665086042098252335883
e = 3
ct = 243251053617903760309941844835411292373350655973075480264001352919865180151222189820473358411037759381328642957324889519192337152355302808400638052620580409813222660643570085177957

Bài này số mũ lập mã $e=3$ bé nên ta có thể dùng hàm `iroot` của `gmpy2` để lấy căn bậc 3.

Code giải:

from Cryptodome.Util.number import *
from sage.all import *
from gmpy2 import *
ct = 243251053617903760309941844835411292373350655973075480264001352919865180151222189820473358411037759381328642957324889519192337152355302808400638052620580409813222660643570085177957
plaintext=gmpy2.iroot(ct,3)[0]
flag=long_to_bytes(plaintext)
print(flag)

`crypto{N33d_m04R_p4dd1ng}`
Nhưng cách này thì khá may rủi, thực ra lí do mà mình ra được đúng flag là vì trong bài thì $ct$ đúng bằng $m^{3}$ mà không bị reduced modulo $n$. Nếu như $m^{3}>n$ và lấy modulo $n$ thì cách trên phá sản.

Nếu trường hợp như trên xảy ra thì ta sẽ cộng dần một bội nguyên dương của $n$ vào $ct$ cho tới khi ra đúng một số lập phương.

## Everything is Big
Source code của bài:

#!/usr/bin/env python3

from Crypto.Util.number import getPrime, bytes_to_long

FLAG = b"crypto{?????????????????????????}"

m = bytes_to_long(FLAG)

def get_huge_RSA():
    p = getPrime(1024)
    q = getPrime(1024)
    N = p*q
    phi = (p-1)*(q-1)
    while True:
        d = getPrime(256)
        e = pow(d,-1,phi)
        if e.bit_length() == N.bit_length():
            break
    return N,e


N, e = get_huge_RSA()
c = pow(m, e, N)

print(f'N = {hex(N)}')
print(f'e = {hex(e)}')
print(f'c = {hex(c)}')

Đối với bài này ta để ý rằng khóa bí mật $d$ được khởi tạo trước từ đầu và ta dễ dàng kiểm tra điều kiện của $d$ thỏa mãn để ta sử dụng Wiener's Attack.

Trước tiên ta cài thư viện ở đây để attack: https://github.com/orisano/owiener

Chi tiết về cơ sở toán học của thuật toán mọi người có thể xem ở đây: https://hackmd.io/@dvck13/rydikXp1ke

Code giải:

import owiener
from Cryptodome.Util.number import *

e = 0x9ab58dbc8049b574c361573955f08ea69f97ecf37400f9626d8f5ac55ca087165ce5e1f459ef6fa5f158cc8e75cb400a7473e89dd38922ead221b33bc33d6d716fb0e4e127b0fc18a197daf856a7062b49fba7a86e3a138956af04f481b7a7d481994aeebc2672e500f3f6d8c581268c2cfad4845158f79c2ef28f242f4fa8f6e573b8723a752d96169c9d885ada59cdeb6dbe932de86a019a7e8fc8aeb07748cfb272bd36d94fe83351252187c2e0bc58bb7a0a0af154b63397e6c68af4314601e29b07caed301b6831cf34caa579eb42a8c8bf69898d04b495174b5d7de0f20cf2b8fc55ed35c6ad157d3e7009f16d6b61786ee40583850e67af13e9d25be3
n = 0xb8af3d3afb893a602de4afe2a29d7615075d1e570f8bad8ebbe9b5b9076594cf06b6e7b30905b6420e950043380ea746f0a14dae34469aa723e946e484a58bcd92d1039105871ffd63ffe64534b7d7f8d84b4a569723f7a833e6daf5e182d658655f739a4e37bd9f4a44aff6ca0255cda5313c3048f56eed5b21dc8d88bf5a8f8379eac83d8523e484fa6ae8dbcb239e65d3777829a6903d779cd2498b255fcf275e5f49471f35992435ee7cade98c8e82a8beb5ce1749349caa16759afc4e799edb12d299374d748a9e3c82e1cc983cdf9daec0a2739dadcc0982c1e7e492139cbff18c5d44529407edfd8e75743d2f51ce2b58573fea6fbd4fe25154b9964d
d = owiener.attack(e, n)

if d is None:
    print("Failed")
else:
    print("Hacked d={}".format(d))
c=0x3f984ff5244f1836ed69361f29905ca1ae6b3dcf249133c398d7762f5e277919174694293989144c9d25e940d2f66058b2289c75d1b8d0729f9a7c4564404a5fd4313675f85f31b47156068878e236c5635156b0fa21e24346c2041ae42423078577a1413f41375a4d49296ab17910ae214b45155c4570f95ca874ccae9fa80433a1ab453cbb28d780c2f1f4dc7071c93aff3924d76c5b4068a0371dff82531313f281a8acadaa2bd5078d3ddcefcb981f37ff9b8b14c7d9bf1accffe7857160982a2c7d9ee01d3e82265eec9c7401ecc7f02581fd0d912684f42d1b71df87a1ca51515aab4e58fab4da96e154ea6cdfb573a71d81b2ea4a080a1066e1bc3474   
m=pow(c,d,n)
print(long_to_bytes(m))

## Crossed Wires
Source code của bài:

from Crypto.Util.number import getPrime, long_to_bytes, bytes_to_long, inverse
import math
from gmpy2 import next_prime

FLAG = b"crypto{????????????????????????????????????????????????}"

p = getPrime(1024)
q = getPrime(1024)
N = p*q
phi = (p-1)*(q-1)
e = 0x10001
d = inverse(e, phi)

my_key = (N, d)

friends = 5
friend_keys = [(N, getPrime(17)) for _ in range(friends)]

cipher = bytes_to_long(FLAG)

for key in friend_keys:
    cipher = pow(cipher, key[1], key[0])

print(f"My private key: {my_key}")
print(f"My Friend's public keys: {friend_keys}")
print(f"Encrypted flag: {cipher}")

Và một file output.txt

My private key: (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 2734411677251148030723138005716109733838866545375527602018255159319631026653190783670493107936401603981429171880504360560494771017246468702902647370954220312452541342858747590576273775107870450853533717116684326976263006435733382045807971890762018747729574021057430331778033982359184838159747331236538501849965329264774927607570410347019418407451937875684373454982306923178403161216817237890962651214718831954215200637651103907209347900857824722653217179548148145687181377220544864521808230122730967452981435355334932104265488075777638608041325256776275200067541533022527964743478554948792578057708522350812154888097)
My Friend's public keys: [(21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 106979), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 108533), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 69557), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 97117), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 103231)]
Encrypted flag: 20304610279578186738172766224224793119885071262464464448863461184092225736054747976985179673905441502689126216282897704508745403799054734121583968853999791604281615154100736259131453424385364324630229671185343778172807262640709301838274824603101692485662726226902121105591137437331463201881264245562214012160875177167442010952439360623396658974413900469093836794752270399520074596329058725874834082188697377597949405779039139194196065364426213208345461407030771089787529200057105746584493554722790592530472869581310117300343461207750821737840042745530876391793484035024644475535353227851321505537398888106855012746117

Về cơ bản thì ở bài này ta được cho biết cả 2 cặp khóa private và public $(N,e,d)$ và được cho thêm 5 cặp public key khác từ Friends như sau: `friend_keys = [(N, getPrime(17)) for _ in range(friends)]`

Điểm đáng nói ở bài này là tất cả dùng chung một modulo là $N$ cho nên ta chỉ cần phân tích được $N$ là có thể decrypt ra được flag. Để phân tích $N$ ta sử dụng thuật toán ở đây: [Factor N given d](https://www.di-mgt.com.au/rsa_factorize_n.html)


Script cho thuật như sau:

from Cryptodome.Util.number import *
from sage.misc.prandom import randint
from sage.all import *
def factor_modulo(N,e,d):
    k=d*e-1
    while True:
        t=k
        g=randint(2,N-1) % N 
        while t%2==0:
            t=t//2
            x=pow(g,t,N)
            y=gcd(x-1,N)
            if (x > 1 and y > 1):
                p=y
                q=int(N)//int(p)
                return int(p),int(q)

N=21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771
d=2734411677251148030723138005716109733838866545375527602018255159319631026653190783670493107936401603981429171880504360560494771017246468702902647370954220312452541342858747590576273775107870450853533717116684326976263006435733382045807971890762018747729574021057430331778033982359184838159747331236538501849965329264774927607570410347019418407451937875684373454982306923178403161216817237890962651214718831954215200637651103907209347900857824722653217179548148145687181377220544864521808230122730967452981435355334932104265488075777638608041325256776275200067541533022527964743478554948792578057708522350812154888097
e=0x10001
p,q=factor_modulo(N,e,d)
print(p)
print(q)

Nhưng trên thực tế ta không cần phải factor $N$ ra để tính private key cho bài này.

Ví dụ trong trường hợp ta có sẵn $\displaystyle ( N,e,d)$ và ta muốn encrypt một plaintext sử dụng một public key khác, ta tạm gọi public key đó là $\displaystyle e'$. Thì lúc này ta có

$$\begin{equation*}
c=m^{e'}
\end{equation*}$$

Ta đã biết $\displaystyle e,d$ thì ta có thể tính được $\displaystyle ed-1=k\varphi ( N)$ và nếu ta tính nghịch đảo của $\displaystyle e'$ theo modulo $\displaystyle k\varphi ( N)$ là $\displaystyle d'$ chẳng hạn thì ta sẽ có

$$\begin{equation*}
e'd'\equiv 1(\bmod k\varphi ( N))
\end{equation*}$$

Lúc này ta được

$$\begin{equation*}
c^{d'} =m^{e'd'} \equiv m^{1+k\varphi ( N)} \equiv m\bmod N
\end{equation*}$$

Ta sử dụng tính chất $\displaystyle a^{b} \equiv a^{c}\bmod N$ thì $\displaystyle b\equiv c(\bmod \varphi ( N))$ và ngoài ra do $\displaystyle ( m,N) =1$ cho nên $\displaystyle \left( m^{k} ,N\right) =1$ và ta có được đẳng thức ở trên.

Cuối cùng script giải bài này sẽ như sau:

from Cryptodome.Util.number import *
from sage.misc.prandom import randint
from sage.all import *
N=21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771
d=2734411677251148030723138005716109733838866545375527602018255159319631026653190783670493107936401603981429171880504360560494771017246468702902647370954220312452541342858747590576273775107870450853533717116684326976263006435733382045807971890762018747729574021057430331778033982359184838159747331236538501849965329264774927607570410347019418407451937875684373454982306923178403161216817237890962651214718831954215200637651103907209347900857824722653217179548148145687181377220544864521808230122730967452981435355334932104265488075777638608041325256776275200067541533022527964743478554948792578057708522350812154888097
e=0x10001
keys = [106979, 108533, 69557, 97117, 103231]
encflag=20304610279578186738172766224224793119885071262464464448863461184092225736054747976985179673905441502689126216282897704508745403799054734121583968853999791604281615154100736259131453424385364324630229671185343778172807262640709301838274824603101692485662726226902121105591137437331463201881264245562214012160875177167442010952439360623396658974413900469093836794752270399520074596329058725874834082188697377597949405779039139194196065364426213208345461407030771089787529200057105746584493554722790592530472869581310117300343461207750821737840042745530876391793484035024644475535353227851321505537398888106855012746117
prod=1
for k in keys:
    prod*=k
dd=inverse(prod,e*d-1)
m=pow(encflag,dd,N)
print(long_to_bytes(m))

## Everything is Still Big

Bài cho ta một file python 

#!/usr/bin/env python3

from Crypto.Util.number import getPrime, bytes_to_long, inverse
from random import getrandbits
from math import gcd

FLAG = b"crypto{?????????????????????????????????????}"

m = bytes_to_long(FLAG)

def get_huge_RSA():
p = getPrime(1024)
q = getPrime(1024)
N = p*q
phi = (p-1)*(q-1)
while True:
d = getrandbits(512)
if (3*d)**4 > N and gcd(d,phi) == 1:
e = inverse(d, phi)
break
return N,e

N, e = get_huge_RSA()
c = pow(m, e, N)

print(f'N = {hex(N)}')
print(f'e = {hex(e)}')
print(f'c = {hex(c)}')

Và một file output.txt

N = 0xb12746657c720a434861e9a4828b3c89a6b8d4a1bd921054e48d47124dbcc9cfcdcc39261c5e93817c167db818081613f57729e0039875c72a5ae1f0bc5ef7c933880c2ad528adbc9b1430003a491e460917b34c4590977df47772fab1ee0ab251f94065ab3004893fe1b2958008848b0124f22c4e75f60ed3889fb62e5ef4dcc247a3d6e23072641e62566cd96ee8114b227b8f498f9a578fc6f687d07acdbb523b6029c5bbeecd5efaf4c4d35304e5e6b5b95db0e89299529eb953f52ca3247d4cd03a15939e7d638b168fd00a1cb5b0cc5c2cc98175c1ad0b959c2ab2f17f917c0ccee8c3fe589b4cb441e817f75e575fc96a4fe7bfea897f57692b050d2b
e = 0x9d0637faa46281b533e83cc37e1cf5626bd33f712cc1948622f10ec26f766fb37b9cd6c7a6e4b2c03bce0dd70d5a3a28b6b0c941d8792bc6a870568790ebcd30f40277af59e0fd3141e272c48f8e33592965997c7d93006c27bf3a2b8fb71831dfa939c0ba2c7569dd1b660efc6c8966e674fbe6e051811d92a802c789d895f356ceec9722d5a7b617d21b8aa42dd6a45de721953939a5a81b8dffc9490acd4f60b0c0475883ff7e2ab50b39b2deeedaefefffc52ae2e03f72756d9b4f7b6bd85b1a6764b31312bc375a2298b78b0263d492205d2a5aa7a227abaf41ab4ea8ce0e75728a5177fe90ace36fdc5dba53317bbf90e60a6f2311bb333bf55ba3245f
c = 0xa3bce6e2e677d7855a1a7819eb1879779d1e1eefa21a1a6e205c8b46fdc020a2487fdd07dbae99274204fadda2ba69af73627bdddcb2c403118f507bca03cb0bad7a8cd03f70defc31fa904d71230aab98a10e155bf207da1b1cac1503f48cab3758024cc6e62afe99767e9e4c151b75f60d8f7989c152fdf4ff4b95ceed9a7065f38c68dee4dd0da503650d3246d463f504b36e1d6fafabb35d2390ecf0419b2bb67c4c647fb38511b34eb494d9289c872203fa70f4084d2fa2367a63a8881b74cc38730ad7584328de6a7d92e4ca18098a15119baee91237cea24975bdfc19bdbce7c1559899a88125935584cd37c8dd31f3f2b4517eefae84e7e588344fa5

Ở bài này ta thấy khóa bí mật $d$ vẫn khá nhỏ so với modulo $N$ nhưng có thêm điều kiện $\displaystyle 3d^{4}  >N$ nên ta không thể sử dụng Wiener's Attack được mà phải chuyển sang sử dụng một thuật toán khác. Ở đây mình sử dụng thuật Boneh & Durfee RSA Low Private Exponent Recovery. Cụ thể code để implement thuật như dưới đây, được mình lấy từ trang https://github.com/jvdsn/crypto-attacks/blob/master/attacks/rsa/boneh_durfee.py

import logging
import os
import sys

from sage.all import RR
from sage.all import ZZ

path = os.path.dirname(os.path.dirname(os.path.dirname(os.path.realpath(os.path.abspath(__file__)))))
if sys.path[1] != path:
sys.path.insert(1, path)

from attacks.factorization import known_phi
from shared.small_roots import herrmann_may

def attack(N, e, factor_bit_length, partial_p=None, delta=0.25, m=1, t=None):
"""
Recovers the prime factors if the private exponent is too small.
This implementation exploits knowledge of least significant bits of prime factors, if available.
More information: Boneh D., Durfee G., "Cryptanalysis of RSA with Private Key d Less than N^0.292"
:param N: the modulus
:param e: the public exponent
:param factor_bit_length: the bit length of the prime factors
:param partial_p: the partial prime factor p (PartialInteger) (default: None)
:param delta: a predicted bound on the private exponent (d < N^delta) (default: 0.25)
:param m: the m value to use for the small roots method (default: 1)
:param t: the t value to use for the small roots method (default: automatically computed using m)
:return: a tuple containing the prime factors, or None if the factors were not found
"""
# Use additional information about factors to speed up Boneh-Durfee.
p_lsb, p_lsb_bit_length = (0, 0) if partial_p is None else partial_p.get_known_lsb()
q_lsb = (pow(p_lsb, -1, 2 ** p_lsb_bit_length) * N) % (2 ** p_lsb_bit_length)
A = ((N >> p_lsb_bit_length) + pow(2, -p_lsb_bit_length, e) * (p_lsb * q_lsb - p_lsb - q_lsb + 1))

x, y = ZZ["x", "y"].gens()
f = x * (A + y) + pow(2, -p_lsb_bit_length, e)
X = int(RR(e) ** delta)
Y = int(2 ** (factor_bit_length - p_lsb_bit_length + 1))
t = int((1 - 2 * delta) * m) if t is None else t
logging.info(f"Trying {m = }, {t = }...")
for x0, y0 in herrmann_may.modular_bivariate(f, e, m, t, X, Y):
z = int(f(x0, y0))
if z % e == 0:
k = pow(x0, -1, e)
s = (N + 1 + k) % e
phi = N - s + 1
factors = known_phi.factorize(N, phi)
if factors:
return factors

return None

def attack_multi_prime(N, e, factor_bit_length, factors, delta=0.25, m=1, t=None):
"""
Recovers the prime factors if the private exponent is too small.
This method works for a modulus consisting of any number of primes.
:param N: the modulus
:param e: the public exponent
:param factor_bit_length: the bit length of the prime factors
:param factors: the number of prime factors in the modulus
:param delta: a predicted bound on the private exponent (d < n^delta) (default: 0.25)
:param m: the m value to use for the small roots method (default: 1)
:param t: the t value to use for the small roots method (default: automatically computed using m)
:return: a tuple containing the prime factors, or None if the factors were not found
"""
x, y = ZZ["x", "y"].gens()
A = N + 1
f = x * (A + y) + 1
X = int(RR(e) ** delta)
Y = int(2 ** ((factors - 1) * factor_bit_length + 1))
t = int((1 - 2 * delta) * m) if t is None else t
logging.info(f"Trying {m = }, {t = }...")
for x0, y0 in herrmann_may.modular_bivariate(f, e, m, t, X, Y):
z = int(f(x0, y0))
if z % e == 0:
k = pow(x0, -1, e)
s = (N + 1 + k) % e
phi = N - s + 1
factors = known_phi.factorize_multi_prime(N, phi)
if factors:
return factors

return None

import logging

# Some logging so we can see what's happening.
logging.basicConfig(level=logging.DEBUG)

N = 0xb12746657c720a434861e9a4828b3c89a6b8d4a1bd921054e48d47124dbcc9cfcdcc39261c5e93817c167db818081613f57729e0039875c72a5ae1f0bc5ef7c933880c2ad528adbc9b1430003a491e460917b34c4590977df47772fab1ee0ab251f94065ab3004893fe1b2958008848b0124f22c4e75f60ed3889fb62e5ef4dcc247a3d6e23072641e62566cd96ee8114b227b8f498f9a578fc6f687d07acdbb523b6029c5bbeecd5efaf4c4d35304e5e6b5b95db0e89299529eb953f52ca3247d4cd03a15939e7d638b168fd00a1cb5b0cc5c2cc98175c1ad0b959c2ab2f17f917c0ccee8c3fe589b4cb441e817f75e575fc96a4fe7bfea897f57692b050d2b
e = 0x9d0637faa46281b533e83cc37e1cf5626bd33f712cc1948622f10ec26f766fb37b9cd6c7a6e4b2c03bce0dd70d5a3a28b6b0c941d8792bc6a870568790ebcd30f40277af59e0fd3141e272c48f8e33592965997c7d93006c27bf3a2b8fb71831dfa939c0ba2c7569dd1b660efc6c8966e674fbe6e051811d92a802c789d895f356ceec9722d5a7b617d21b8aa42dd6a45de721953939a5a81b8dffc9490acd4f60b0c0475883ff7e2ab50b39b2deeedaefefffc52ae2e03f72756d9b4f7b6bd85b1a6764b31312bc375a2298b78b0263d492205d2a5aa7a227abaf41ab4ea8ce0e75728a5177fe90ace36fdc5dba53317bbf90e60a6f2311bb333bf55ba3245f
p_bits = 1024
delta = 0.26

p, q = attack(N, e, p_bits, delta=delta, m=3)
assert p * q == N
print(f"Found {p = } and {q = }")

Sau khi tìm được $p,q$ thì mình tìm $d$ để giải ra flag thôi 

from Cryptodome.Util.number import *
p=126941806460244095377115101056215170200213929484090514615615360791047815508282999312547430020357429932308768712158161906404559758053111268332560036207583087350177765905028171368043071041697143783557751018420251412743117633405829486334952312669390185416378995607092112979722242788438125727258195819223984881293
q=176171647623796415963359037459080158279832338949959164916683927127298628490481547783271812783698644240568426097637418877451963005025506022174220789400439434207167210194263661330803801184790705595672502832081604208722809411817374316086936064983248582792693864440342630864686435882656704880417413599728301262999
N = 0xb12746657c720a434861e9a4828b3c89a6b8d4a1bd921054e48d47124dbcc9cfcdcc39261c5e93817c167db818081613f57729e0039875c72a5ae1f0bc5ef7c933880c2ad528adbc9b1430003a491e460917b34c4590977df47772fab1ee0ab251f94065ab3004893fe1b2958008848b0124f22c4e75f60ed3889fb62e5ef4dcc247a3d6e23072641e62566cd96ee8114b227b8f498f9a578fc6f687d07acdbb523b6029c5bbeecd5efaf4c4d35304e5e6b5b95db0e89299529eb953f52ca3247d4cd03a15939e7d638b168fd00a1cb5b0cc5c2cc98175c1ad0b959c2ab2f17f917c0ccee8c3fe589b4cb441e817f75e575fc96a4fe7bfea897f57692b050d2b
e = 0x9d0637faa46281b533e83cc37e1cf5626bd33f712cc1948622f10ec26f766fb37b9cd6c7a6e4b2c03bce0dd70d5a3a28b6b0c941d8792bc6a870568790ebcd30f40277af59e0fd3141e272c48f8e33592965997c7d93006c27bf3a2b8fb71831dfa939c0ba2c7569dd1b660efc6c8966e674fbe6e051811d92a802c789d895f356ceec9722d5a7b617d21b8aa42dd6a45de721953939a5a81b8dffc9490acd4f60b0c0475883ff7e2ab50b39b2deeedaefefffc52ae2e03f72756d9b4f7b6bd85b1a6764b31312bc375a2298b78b0263d492205d2a5aa7a227abaf41ab4ea8ce0e75728a5177fe90ace36fdc5dba53317bbf90e60a6f2311bb333bf55ba3245f
c = 0xa3bce6e2e677d7855a1a7819eb1879779d1e1eefa21a1a6e205c8b46fdc020a2487fdd07dbae99274204fadda2ba69af73627bdddcb2c403118f507bca03cb0bad7a8cd03f70defc31fa904d71230aab98a10e155bf207da1b1cac1503f48cab3758024cc6e62afe99767e9e4c151b75f60d8f7989c152fdf4ff4b95ceed9a7065f38c68dee4dd0da503650d3246d463f504b36e1d6fafabb35d2390ecf0419b2bb67c4c647fb38511b34eb494d9289c872203fa70f4084d2fa2367a63a8881b74cc38730ad7584328de6a7d92e4ca18098a15119baee91237cea24975bdfc19bdbce7c1559899a88125935584cd37c8dd31f3f2b4517eefae84e7e588344fa5
phi=(p-1)*(q-1)
d=inverse(e,phi)
m=pow(c,d,N)
print(long_to_bytes(m))

Về cơ sở toán học của thuật toán trên, mọi người tham khảo tại đây: https://link.springer.com/content/pdf/10.1007/3-540-48910-X_1.pdf

## Endless Emails
Chall cho ta một file python như sau:

#!/usr/bin/env python3

from Crypto.Util.number import bytes_to_long, getPrime
from secret import messages


def RSA_encrypt(message):
    m = bytes_to_long(message)
    p = getPrime(1024)
    q = getPrime(1024)
    N = p * q
    e = 3
    c = pow(m, e, N)
    return N, e, c


for m in messages:
    N, e, c = RSA_encrypt(m)
    print(f"n = {N}")
    print(f"e = {e}")
    print(f"c = {c}")

Và một file output.txt

n = 14528915758150659907677315938876872514853653132820394367681510019000469589767908107293777996420037715293478868775354645306536953789897501630398061779084810058931494642860729799059325051840331449914529594113593835549493208246333437945551639983056810855435396444978249093419290651847764073607607794045076386643023306458718171574989185213684263628336385268818202054811378810216623440644076846464902798568705083282619513191855087399010760232112434412274701034094429954231366422968991322244343038458681255035356984900384509158858007713047428143658924970374944616430311056440919114824023838380098825914755712289724493770021
e = 3
c = 6965891612987861726975066977377253961837139691220763821370036576350605576485706330714192837336331493653283305241193883593410988132245791554283874785871849223291134571366093850082919285063130119121338290718389659761443563666214229749009468327825320914097376664888912663806925746474243439550004354390822079954583102082178617110721589392875875474288168921403550415531707419931040583019529612270482482718035497554779733578411057633524971870399893851589345476307695799567919550426417015815455141863703835142223300228230547255523815097431420381177861163863791690147876158039619438793849367921927840731088518955045807722225


n = 20463913454649855046677206889944639231694511458416906994298079596685813354570085475890888433776403011296145408951323816323011550738170573801417972453504044678801608709931200059967157605416809387753258251914788761202456830940944486915292626560515250805017229876565916349963923702612584484875113691057716315466239062005206014542088484387389725058070917118549621598629964819596412564094627030747720659155558690124005400257685883230881015636066183743516494701900125788836869358634031031172536767950943858472257519195392986989232477630794600444813136409000056443035171453870906346401936687214432176829528484662373633624123
e = 3
c = 5109363605089618816120178319361171115590171352048506021650539639521356666986308721062843132905170261025772850941702085683855336653472949146012700116070022531926476625467538166881085235022484711752960666438445574269179358850309578627747024264968893862296953506803423930414569834210215223172069261612934281834174103316403670168299182121939323001232617718327977313659290755318972603958579000300780685344728301503641583806648227416781898538367971983562236770576174308965929275267929379934367736694110684569576575266348020800723535121638175505282145714117112442582416208209171027273743686645470434557028336357172288865172


n = 19402640770593345339726386104915705450969517850985511418263141255686982818547710008822417349818201858549321868878490314025136645036980129976820137486252202687238348587398336652955435182090722844668488842986318211649569593089444781595159045372322540131250208258093613844753021272389255069398553523848975530563989367082896404719544411946864594527708058887475595056033713361893808330341623804367785721774271084389159493974946320359512776328984487126583015777989991635428744050868653379191842998345721260216953918203248167079072442948732000084754225272238189439501737066178901505257566388862947536332343196537495085729147
e = 3
c = 5603386396458228314230975500760833991383866638504216400766044200173576179323437058101562931430558738148852367292802918725271632845889728711316688681080762762324367273332764959495900563756768440309595248691744845766607436966468714038018108912467618638117493367675937079141350328486149333053000366933205635396038539236203203489974033629281145427277222568989469994178084357460160310598260365030056631222346691527861696116334946201074529417984624304973747653407317290664224507485684421999527164122395674469650155851869651072847303136621932989550786722041915603539800197077294166881952724017065404825258494318993054344153


n = 12005639978012754274325188681720834222130605634919280945697102906256738419912110187245315232437501890545637047506165123606573171374281507075652554737014979927883759915891863646221205835211640845714836927373844277878562666545230876640830141637371729405545509920889968046268135809999117856968692236742804637929866632908329522087977077849045608566911654234541526643235586433065170392920102840518192803854740398478305598092197183671292154743153130012885747243219372709669879863098708318993844005566984491622761795349455404952285937152423145150066181043576492305166964448141091092142224906843816547235826717179687198833961
e = 3
c = 1522280741383024774933280198410525846833410931417064479278161088248621390305797210285777845359812715909342595804742710152832168365433905718629465545306028275498667935929180318276445229415104842407145880223983428713335709038026249381363564625791656631137936935477777236936508600353416079028339774876425198789629900265348122040413865209592074731028757972968635601695468594123523892918747882221891834598896483393711851510479989203644477972694520237262271530260496342247355761992646827057846109181410462131875377404309983072358313960427035348425800940661373272947647516867525052504539561289941374722179778872627956360577


n = 17795451956221451086587651307408104001363221003775928432650752466563818944480119932209305765249625841644339021308118433529490162294175590972336954199870002456682453215153111182451526643055812311071588382409549045943806869173323058059908678022558101041630272658592291327387549001621625757585079662873501990182250368909302040015518454068699267914137675644695523752851229148887052774845777699287718342916530122031495267122700912518207571821367123013164125109174399486158717604851125244356586369921144640969262427220828940652994276084225196272504355264547588369516271460361233556643313911651916709471353368924621122725823
e = 3
c = 8752507806125480063647081749506966428026005464325535765874589376572431101816084498482064083887400646438977437273700004934257274516197148448425455243811009944321764771392044345410680448204581679548854193081394891841223548418812679441816502910830861271884276608891963388657558218620911858230760629700918375750796354647493524576614017731938584618983084762612414591830024113057983483156974095503392359946722756364412399187910604029583464521617256125933111786441852765229820406911991809039519015434793656710199153380699319611499255869045311421603167606551250174746275803467549814529124250122560661739949229005127507540805


n = 25252721057733555082592677470459355315816761410478159901637469821096129654501579313856822193168570733800370301193041607236223065376987811309968760580864569059669890823406084313841678888031103461972888346942160731039637326224716901940943571445217827960353637825523862324133203094843228068077462983941899571736153227764822122334838436875488289162659100652956252427378476004164698656662333892963348126931771536472674447932268282205545229907715893139346941832367885319597198474180888087658441880346681594927881517150425610145518942545293750127300041942766820911120196262215703079164895767115681864075574707999253396530263
e = 3
c = 23399624135645767243362438536844425089018405258626828336566973656156553220156563508607371562416462491581383453279478716239823054532476006642583363934314982675152824147243749715830794488268846671670287617324522740126594148159945137948643597981681529145611463534109482209520448640622103718682323158039797577387254265854218727476928164074249568031493984825273382959147078839665114417896463735635546290504843957780546550577300001452747760982468547756427137284830133305010038339400230477403836856663883956463830571934657200851598986174177386323915542033293658596818231793744261192870485152396793393026198817787033127061749


n = 19833203629283018227011925157509157967003736370320129764863076831617271290326613531892600790037451229326924414757856123643351635022817441101879725227161178559229328259469472961665857650693413215087493448372860837806619850188734619829580286541292997729705909899738951228555834773273676515143550091710004139734080727392121405772911510746025807070635102249154615454505080376920778703360178295901552323611120184737429513669167641846902598281621408629883487079110172218735807477275590367110861255756289520114719860000347219161944020067099398239199863252349401303744451903546571864062825485984573414652422054433066179558897
e = 3
c = 15239683995712538665992887055453717247160229941400011601942125542239446512492703769284448009141905335544729440961349343533346436084176947090230267995060908954209742736573986319254695570265339469489948102562072983996668361864286444602534666284339466797477805372109723178841788198177337648499899079471221924276590042183382182326518312979109378616306364363630519677884849945606288881683625944365927809405420540525867173639222696027472336981838588256771671910217553150588878434061862840893045763456457939944572192848992333115479951110622066173007227047527992906364658618631373790704267650950755276227747600169403361509144

Như đã thấy trong bài thì đây là hệ mật mã RSA nhưng có số mũ lập mã $\displaystyle e$ bé, cụ thể là $\displaystyle e=3$. Ngoài ra ta còn biết thêm thông tin là có một vài plaintext trong số 5 plaintext ở trên bị lặp lại tức là có một số $\displaystyle m$ để mà

$$\begin{equation*}
c_{i} =m^{3}(\bmod n_{i})
\end{equation*}$$

trong đó $\displaystyle i$ chạy trên một họ tập hợp nào đó.

Bây giờ ta sẽ nói về thuật toán để giải quyết bài toán trên. Đầu tiên ta giả sử có tình huống mà ba người tham gia chọn ba khóa công khai là $\displaystyle ( n_{1} ,e) ,( n_{2} ,e) ,( n_{3} ,e)$ với $\displaystyle e=3$. Và ta muốn gửi một đoạn tin nhắn $\displaystyle x$ đến cho cả ba người đó thì ta sẽ sử dụng khóa công khai là $\displaystyle e$ để tính toán $\displaystyle c_{1} \equiv x^{3}\bmod n_{1}$ và tương tự như vậy với $\displaystyle c_{2} ,c_{3}$. Nhiệm vụ của ta bây giờ là sử dụng định lí thặng dư Trung Hoa để tính toán

$$\begin{equation*}
\begin{cases}
m\equiv c_{1}(\bmod n_{1})\\
m\equiv c_{2}(\bmod n_{2})\\
m\equiv c_{3}(\bmod n_{3})
\end{cases}
\end{equation*}$$

Hệ sẽ có họ nghiệm duy nhất theo modulo $\displaystyle n_{1} n_{2} n_{3}$ dẫn tới $\displaystyle m=x^{3} +kn_{1} n_{2} n_{3} ,k\in \mathbb{Z}^{*}$ nhưng ta có $\displaystyle x\leqslant n_{i} ,\forall i$ cho nên $\displaystyle x^{3} \leqslant n_{1} n_{2} n_{3}$ kéo theo $\displaystyle m=x^{3}$.

Như vậy ta sẽ chọn ra cặp 3 số bất kì từ 5 số ở trên và giải hệ phương trình thặng dư cho tới khi ra được flag. Tổng cộng ta cần giải $\displaystyle \binom{7}{3}$ hệ phương trình.

Thuật toán trên là một trường hợp đặc biệt của Hastad Broadcast Attack

Code giải như sau :

from Cryptodome.Util.number import *
from sage.all import *
from itertools import combinations
from sympy.ntheory.modular import crt
from gmpy2 import iroot



def extract_nc_pairs(file_path):
    nc_pairs = []
    with open(file_path, 'r') as file:
        lines = file.readlines()

    n = c = None
    for line in lines:
        line = line.strip()
        if line.startswith("n ="):
            n = int(line.split("=", 1)[1].strip())
        elif line.startswith("c ="):
            c = int(line.split("=", 1)[1].strip())
        if n is not None and c is not None:
            nc_pairs.append((n, c))
            n = c = None

    return nc_pairs

def find_m_with_nc(nc_pairs):
    for combo in combinations(nc_pairs, 3):
        moduli = [n for n, c in combo]
        remainders = [c for n, c in combo]
        result = crt(moduli, remainders)
        if result is not None:
            m = result[0]  
            root, is_exact = iroot(m, 3)
            if is_exact:
                decode_message=long_to_bytes(int(root))
                print(f"m = {m}, cube root = {int(root)}")
                print(f"Flag là: {decode_message}")

file_path = "/home/duc112006/cryptohack/RSA/publicexp/output.txt"
nc_pairs = extract_nc_pairs(file_path)
find_m_with_nc(nc_pairs)

# Primes Part 2

## Infinite Descent

Chall cho ta một file python như sau :

#!/usr/bin/env python3

import random
from Crypto.Util.number import bytes_to_long, isPrime

FLAG = b"crypto{???????????????????}"


def getPrimes(bitsize):
    r = random.getrandbits(bitsize)
    p, q = r, r
    while not isPrime(p):
        p += random.getrandbits(bitsize//4)
    while not isPrime(q):
        q += random.getrandbits(bitsize//8)
    return p, q


m = bytes_to_long(FLAG)
p, q = getPrimes(2048)
n = p * q
e = 0x10001
c = pow(m, e, n)

print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")

Và một file output.txt

n = 383347712330877040452238619329524841763392526146840572232926924642094891453979246383798913394114305368360426867021623649667024217266529000859703542590316063318592391925062014229671423777796679798747131250552455356061834719512365575593221216339005132464338847195248627639623487124025890693416305788160905762011825079336880567461033322240015771102929696350161937950387427696385850443727777996483584464610046380722736790790188061964311222153985614287276995741553706506834906746892708903948496564047090014307484054609862129530262108669567834726352078060081889712109412073731026030466300060341737504223822014714056413752165841749368159510588178604096191956750941078391415634472219765129561622344109769892244712668402761549412177892054051266761597330660545704317210567759828757156904778495608968785747998059857467440128156068391746919684258227682866083662345263659558066864109212457286114506228470930775092735385388316268663664139056183180238043386636254075940621543717531670995823417070666005930452836389812129462051771646048498397195157405386923446893886593048680984896989809135802276892911038588008701926729269812453226891776546037663583893625479252643042517196958990266376741676514631089466493864064316127648074609662749196545969926051
e = 65537
c = 98280456757136766244944891987028935843441533415613592591358482906016439563076150526116369842213103333480506705993633901994107281890187248495507270868621384652207697607019899166492132408348789252555196428608661320671877412710489782358282011364127799563335562917707783563681920786994453004763755404510541574502176243896756839917991848428091594919111448023948527766368304503100650379914153058191140072528095898576018893829830104362124927140555107994114143042266758709328068902664037870075742542194318059191313468675939426810988239079424823495317464035252325521917592045198152643533223015952702649249494753395100973534541766285551891859649320371178562200252228779395393974169736998523394598517174182142007480526603025578004665936854657294541338697513521007818552254811797566860763442604365744596444735991732790926343720102293453429936734206246109968817158815749927063561835274636195149702317415680401987150336994583752062565237605953153790371155918439941193401473271753038180560129784192800351649724465553733201451581525173536731674524145027931923204961274369826379325051601238308635192540223484055096203293400419816024111797903442864181965959247745006822690967920957905188441550106930799896292835287867403979631824085790047851383294389

Vấn đề của bài này nằm ở đoạn code: ```p += random.getrandbits(bitsize//4)``` và ```q += random.getrandbits(bitsize//8)```. Tức là nếu như $p$ không là số nguyên tố thì khi đó ta sẽ cộng thêm $p$ bởi một giá có độ lớn bằng với `bitsize//4` và tiếp tục cho tới khi $p$ là số nguyên tố.
Với cách định nghĩa $p,q$ như vậy thì ta có thể nhận thấy rằng $p,q$ khá gần nhau và ta có thể thử khai thác giả thiết này để phân tích được $n$.
Tham khảo tại link sau: [RSA and prime difference](https://crypto.stackexchange.com/questions/5262/rsa-and-prime-difference)

Sau một hồi tìm hiểu thì mình biết được bài này sẽ sử dụng thuật Fermat's Factorization tại đây: [Fermat's Method](https://eprint.iacr.org/2009/318.pdf)


from Cryptodome.Util.number import *
from sage.all import *
def fermat_factor(n):
    a=ceil(sqrt(n))
    b2= a**2 - n
    while not b2.is_square():
        a+=1
        b2=a**2-n
    b=sqrt(b2)
    p=int(a-b)
    q=int(a+b)
    return [p,q]
n = 383347712330877040452238619329524841763392526146840572232926924642094891453979246383798913394114305368360426867021623649667024217266529000859703542590316063318592391925062014229671423777796679798747131250552455356061834719512365575593221216339005132464338847195248627639623487124025890693416305788160905762011825079336880567461033322240015771102929696350161937950387427696385850443727777996483584464610046380722736790790188061964311222153985614287276995741553706506834906746892708903948496564047090014307484054609862129530262108669567834726352078060081889712109412073731026030466300060341737504223822014714056413752165841749368159510588178604096191956750941078391415634472219765129561622344109769892244712668402761549412177892054051266761597330660545704317210567759828757156904778495608968785747998059857467440128156068391746919684258227682866083662345263659558066864109212457286114506228470930775092735385388316268663664139056183180238043386636254075940621543717531670995823417070666005930452836389812129462051771646048498397195157405386923446893886593048680984896989809135802276892911038588008701926729269812453226891776546037663583893625479252643042517196958990266376741676514631089466493864064316127648074609662749196545969926051
e = 65537
c = 98280456757136766244944891987028935843441533415613592591358482906016439563076150526116369842213103333480506705993633901994107281890187248495507270868621384652207697607019899166492132408348789252555196428608661320671877412710489782358282011364127799563335562917707783563681920786994453004763755404510541574502176243896756839917991848428091594919111448023948527766368304503100650379914153058191140072528095898576018893829830104362124927140555107994114143042266758709328068902664037870075742542194318059191313468675939426810988239079424823495317464035252325521917592045198152643533223015952702649249494753395100973534541766285551891859649320371178562200252228779395393974169736998523394598517174182142007480526603025578004665936854657294541338697513521007818552254811797566860763442604365744596444735991732790926343720102293453429936734206246109968817158815749927063561835274636195149702317415680401987150336994583752062565237605953153790371155918439941193401473271753038180560129784192800351649724465553733201451581525173536731674524145027931923204961274369826379325051601238308635192540223484055096203293400419816024111797903442864181965959247745006822690967920957905188441550106930799896292835287867403979631824085790047851383294389
result=fermat_factor(n)
p=result[0]
q=result[1]
phi=(p-1)*(q-1)
d=int(inverse(e,phi))
m=pow(int(c),d,int(n))
print(long_to_bytes(m))

(các bài tập về RSA trên CryptoHack cũng có khá lâu rồi nên có một số bài tác giả sau khi solve xong thì đẩy database factor(n) lên FactorDB. Kết quả là có vài bài trong phần bài tập giải theo cách này được :))) bài này là một trong số đó)

## Marin's Secrets
Bài cho ta một file source code như sau: 

#!/usr/bin/env python3

import random
from Crypto.Util.number import bytes_to_long
from secret import secrets, flag

def get_prime(secret):
prime = 1
for _ in range(secret):
prime = prime << 1
return prime - 1

random.shuffle(secrets)

m = bytes_to_long(flag)
p = get_prime(secrets[0])
q = get_prime(secrets[1])
n = p * q
e = 0x10001
c = pow(m, e, n)

print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")

Và file output.txt

n: 658416274830184544125027519921443515789888264156074733099244040126213682497714032798116399288176502462829255784525977722903018714434309698108208388664768262754316426220651576623731617882923164117579624827261244506084274371250277849351631679441171018418018498039996472549893150577189302871520311715179730714312181456245097848491669795997289830612988058523968384808822828370900198489249243399165125219244753790779764466236965135793576516193213175061401667388622228362042717054014679032953441034021506856017081062617572351195418505899388715709795992029559042119783423597324707100694064675909238717573058764118893225111602703838080618565401139902143069901117174204252871948846864436771808616432457102844534843857198735242005309073939051433790946726672234643259349535186268571629077937597838801337973092285608744209951533199868228040004432132597073390363357892379997655878857696334892216345070227646749851381208554044940444182864026513709449823489593439017366358869648168238735087593808344484365136284219725233811605331815007424582890821887260682886632543613109252862114326372077785369292570900594814481097443781269562647303671428895764224084402259605109600363098950091998891375812839523613295667253813978434879172781217285652895469194181218343078754501694746598738215243769747956572555989594598180639098344891175879455994652382137038240166358066403475457
e: 65537
c: 400280463088930432319280359115194977582517363610532464295210669530407870753439127455401384569705425621445943992963380983084917385428631223046908837804126399345875252917090184158440305503817193246288672986488987883177380307377025079266030262650932575205141853413302558460364242355531272967481409414783634558791175827816540767545944534238189079030192843288596934979693517964655661507346729751987928147021620165009965051933278913952899114253301044747587310830419190623282578931589587504555005361571572561916866063458812965314474160499067525067495140150092119620928363007467390920130717521169105167963364154636472055084012592138570354390246779276003156184676298710746583104700516466091034510765027167956117869051938116457370384737440965109619578227422049806566060571831017610877072484262724789571076529586427405780121096546942812322324807145137017942266863534989082115189065560011841150908380937354301243153206428896320576609904361937035263985348984794208198892615898907005955403529470847124269512316191753950203794578656029324506688293446571598506042198219080325747328636232040936761788558421528960279832802127562115852304946867628316502959562274485483867481731149338209009753229463924855930103271197831370982488703456463385914801246828662212622006947380115549529820197355738525329885232170215757585685484402344437894981555179129287164971002033759724456

Phân tích đoạn code trên: Hàm `get_prime` sinh ra các số nguyên có dạng $\displaystyle 2^{secret} -1$ và số $\displaystyle n$ của ta cũng có dạng $\displaystyle \left( 2^{a} -1\right)\left( 2^{b} -1\right)$ với $\displaystyle a,b$ được lấy ngẫu nhiên từ secrets. Vấn đề ở đây ta không biết $\displaystyle 2^{a} -1$ và $\displaystyle 2^{b} -1$ có phải là số nguyên tố hay không. Điều kiện cần để $\displaystyle 2^{a} -1$ là một số nguyên tố đó chính là $\displaystyle a$ cũng phải là số nguyên tố. Vậy ta cần phải xác định cách để phân tích $\displaystyle n$ nếu ta biết $\displaystyle n$ có dạng $\displaystyle n=\left( 2^{a} -1\right)\left( 2^{b} -1\right)$.

Trước tiên ta đi giải quyết bài toán dễ trước đó chính là giả sử $\displaystyle 2^{a} -1,2^{b} -1$ đều là các số nguyên tố thì ta sẽ phân tích như thế nào. 

Cách đầu tiên là xài [FactorDb](https://factordb.com/index.php?query=658416274830184544125027519921443515789888264156074733099244040126213682497714032798116399288176502462829255784525977722903018714434309698108208388664768262754316426220651576623731617882923164117579624827261244506084274371250277849351631679441171018418018498039996472549893150577189302871520311715179730714312181456245097848491669795997289830612988058523968384808822828370900198489249243399165125219244753790779764466236965135793576516193213175061401667388622228362042717054014679032953441034021506856017081062617572351195418505899388715709795992029559042119783423597324707100694064675909238717573058764118893225111602703838080618565401139902143069901117174204252871948846864436771808616432457102844534843857198735242005309073939051433790946726672234643259349535186268571629077937597838801337973092285608744209951533199868228040004432132597073390363357892379997655878857696334892216345070227646749851381208554044940444182864026513709449823489593439017366358869648168238735087593808344484365136284219725233811605331815007424582890821887260682886632543613109252862114326372077785369292570900594814481097443781269562647303671428895764224084402259605109600363098950091998891375812839523613295667253813978434879172781217285652895469194181218343078754501694746598738215243769747956572555989594598180639098344891175879455994652382137038240166358066403475457) thì ra luôn 2 thừa số nguyên tố =))

Cụ thể như này: 

from Cryptodome.Util.number import *
n=658416274830184544125027519921443515789888264156074733099244040126213682497714032798116399288176502462829255784525977722903018714434309698108208388664768262754316426220651576623731617882923164117579624827261244506084274371250277849351631679441171018418018498039996472549893150577189302871520311715179730714312181456245097848491669795997289830612988058523968384808822828370900198489249243399165125219244753790779764466236965135793576516193213175061401667388622228362042717054014679032953441034021506856017081062617572351195418505899388715709795992029559042119783423597324707100694064675909238717573058764118893225111602703838080618565401139902143069901117174204252871948846864436771808616432457102844534843857198735242005309073939051433790946726672234643259349535186268571629077937597838801337973092285608744209951533199868228040004432132597073390363357892379997655878857696334892216345070227646749851381208554044940444182864026513709449823489593439017366358869648168238735087593808344484365136284219725233811605331815007424582890821887260682886632543613109252862114326372077785369292570900594814481097443781269562647303671428895764224084402259605109600363098950091998891375812839523613295667253813978434879172781217285652895469194181218343078754501694746598738215243769747956572555989594598180639098344891175879455994652382137038240166358066403475457
e=65537
c=400280463088930432319280359115194977582517363610532464295210669530407870753439127455401384569705425621445943992963380983084917385428631223046908837804126399345875252917090184158440305503817193246288672986488987883177380307377025079266030262650932575205141853413302558460364242355531272967481409414783634558791175827816540767545944534238189079030192843288596934979693517964655661507346729751987928147021620165009965051933278913952899114253301044747587310830419190623282578931589587504555005361571572561916866063458812965314474160499067525067495140150092119620928363007467390920130717521169105167963364154636472055084012592138570354390246779276003156184676298710746583104700516466091034510765027167956117869051938116457370384737440965109619578227422049806566060571831017610877072484262724789571076529586427405780121096546942812322324807145137017942266863534989082115189065560011841150908380937354301243153206428896320576609904361937035263985348984794208198892615898907005955403529470847124269512316191753950203794578656029324506688293446571598506042198219080325747328636232040936761788558421528960279832802127562115852304946867628316502959562274485483867481731149338209009753229463924855930103271197831370982488703456463385914801246828662212622006947380115549529820197355738525329885232170215757585685484402344437894981555179129287164971002033759724456
p=2**2203-1
q=2**2281-1
phi=(p-1)*(q-1)
d=inverse(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))

Bây giờ giả sử như tool của ta không hoạt động thì ta phải làm sao? Các số nguyên tố có dạng $\displaystyle 2^{a} -1$ được gọi là các số nguyên tố Mersenne. Ngoài ra với $\displaystyle n=\left( 2^{a} -1\right)\left( 2^{b} -1\right)$ thì $\displaystyle n\sim 2^{a+b}$ cho nên nếu ta lấy phần nguyên của logarit cơ số 2 của $\displaystyle n$ sẽ ra được tổng của hai số nguyên tố. 

from math import *
n=658416274830184544125027519921443515789888264156074733099244040126213682497714032798116399288176502462829255784525977722903018714434309698108208388664768262754316426220651576623731617882923164117579624827261244506084274371250277849351631679441171018418018498039996472549893150577189302871520311715179730714312181456245097848491669795997289830612988058523968384808822828370900198489249243399165125219244753790779764466236965135793576516193213175061401667388622228362042717054014679032953441034021506856017081062617572351195418505899388715709795992029559042119783423597324707100694064675909238717573058764118893225111602703838080618565401139902143069901117174204252871948846864436771808616432457102844534843857198735242005309073939051433790946726672234643259349535186268571629077937597838801337973092285608744209951533199868228040004432132597073390363357892379997655878857696334892216345070227646749851381208554044940444182864026513709449823489593439017366358869648168238735087593808344484365136284219725233811605331815007424582890821887260682886632543613109252862114326372077785369292570900594814481097443781269562647303671428895764224084402259605109600363098950091998891375812839523613295667253813978434879172781217285652895469194181218343078754501694746598738215243769747956572555989594598180639098344891175879455994652382137038240166358066403475457
print(floor(log2(n)))

print(bin(n)[2:])

Tiếp theo ta viết lại $\displaystyle n=\left( 2^{a} -1\right)\left( 2^{b} -1\right) =2^{a+b} -2^{a} -2^{b} +1=\left( 2^{a+b} -1\right) -\left( 2^{a} -1\right) -\left( 2^{b} -1\right)$. Bây giờ các số $\displaystyle 2^{t} -1$ khi biểu diễn nhị phân chỉ toàn gồm các số 1. Khi đó ta xét $\displaystyle 2^{a+b} -1$ gồm toàn các chữ số 1. Khi ta lấy số trên trừ cho $\displaystyle 2^{a} -1$ thì $\displaystyle a$ bit đầu tiên trong số $\displaystyle a+b$ bit của số $\displaystyle 2^{a+b} -1$ sẽ trở về 0. Sau đó nếu ta lấy số trên trừ tiếp cho $\displaystyle 2^{b} -1$ thì ta sẽ được một số có bit đầu tiên là 1, sau đó tiếp tục đi từ phải sang trái thực hiện phép trừ, nếu như bit bị trừ là 0 thì khi trừ kết quả sẽ ra 0 và nếu bit bị trừ là 1 thì kết quả sẽ trả về 1, phép toán sẽ dừng tại một bit mà kể từ bit đó về sau không còn số 0 nào nữa. Khi viết $\displaystyle n$ về dưới dạng nhị phân ta để ý thấy có một vị trí mà tại đó các bit còn lại không có bit nào bằng 0 nữa 

![image](https://github.com/user-attachments/assets/f4522332-cb52-49a8-9821-316a712c2f4b)

Như vậy ta sẽ lấy các bit ở phía sau số 0 này và chuyển thành số thập phân, tiếp theo lấy phần nguyên của log2 thì sẽ ra được 1 trong 2 số nguyên tố. Tới đây thì ta coi như giải quyết được bài tập. 

from math import *
n=658416274830184544125027519921443515789888264156074733099244040126213682497714032798116399288176502462829255784525977722903018714434309698108208388664768262754316426220651576623731617882923164117579624827261244506084274371250277849351631679441171018418018498039996472549893150577189302871520311715179730714312181456245097848491669795997289830612988058523968384808822828370900198489249243399165125219244753790779764466236965135793576516193213175061401667388622228362042717054014679032953441034021506856017081062617572351195418505899388715709795992029559042119783423597324707100694064675909238717573058764118893225111602703838080618565401139902143069901117174204252871948846864436771808616432457102844534843857198735242005309073939051433790946726672234643259349535186268571629077937597838801337973092285608744209951533199868228040004432132597073390363357892379997655878857696334892216345070227646749851381208554044940444182864026513709449823489593439017366358869648168238735087593808344484365136284219725233811605331815007424582890821887260682886632543613109252862114326372077785369292570900594814481097443781269562647303671428895764224084402259605109600363098950091998891375812839523613295667253813978434879172781217285652895469194181218343078754501694746598738215243769747956572555989594598180639098344891175879455994652382137038240166358066403475457
print(floor(log2(n)))
print(bin(n)[2:])
def binary_to_decimal(binary_str):
return int(binary_str, 2)
binary = "01111111111111111111111111111111111111111111111111111111111111111111111111111110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001"
print(binary_to_decimal(binary))
p=floor(log2(binary_to_decimal(binary)))
print(floor(log2(binary_to_decimal(binary))))
q=floor(log2(n))-p
print(f"2 số nguyên tố cần tìm là {p},{q}")

Một tài liệu khá thú vị [A New Public-Key Cryptosystem via Mersenne Numbers](https://eprint.iacr.org/2017/481.pdf)
## Fast Primes


Source code của bài:

#!/usr/bin/env python3

import math
import random
from Crypto.Cipher import PKCS1_OAEP
from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long, inverse
from gmpy2 import is_prime

FLAG = b"crypto{????????????}"

primes = []

def sieve(maximum=10000):
# In general Sieve of Sundaram, produces primes smaller
# than (2*x + 2) for a number given number x. Since
# we want primes smaller than maximum, we reduce maximum to half
# This array is used to separate numbers of the form
# i+j+2ij from others where 1 <= i <= j
marked = [False]*(int(maximum/2)+1)

# Main logic of Sundaram. Mark all numbers which
# do not generate prime number by doing 2*i+1
for i in range(1, int((math.sqrt(maximum)-1)/2)+1):
for j in range(((i*(i+1)) << 1), (int(maximum/2)+1), (2*i+1)):
marked[j] = True

# Since 2 is a prime number
primes.append(2)

# Print other primes. Remaining primes are of the
# form 2*i + 1 such that marked[i] is false.
for i in range(1, int(maximum/2)):
if (marked[i] == False):
primes.append(2*i + 1)

def get_primorial(n):
result = 1
for i in range(n):
result = result * primes[i]
return result

def get_fast_prime():
M = get_primorial(40)
while True:
k = random.randint(2**28, 2**29-1)
a = random.randint(2**20, 2**62-1)
p = k * M + pow(e, a, M)

if is_prime(p):
return p

sieve()

e = 0x10001
m = bytes_to_long(FLAG)
p = get_fast_prime()
q = get_fast_prime()
n = p * q
phi = (p - 1) * (q - 1)
d = inverse(e, phi)

key = RSA.construct((n, e, d))
cipher = PKCS1_OAEP.new(key)
ciphertext = cipher.encrypt(FLAG)

assert cipher.decrypt(ciphertext) == FLAG

exported = key.publickey().export_key()
with open("key.pem", 'wb') as f:
f.write(exported)

with open('ciphertext.txt', 'w') as f:
f.write(ciphertext.hex())

ciphertext.txt

249d72cd1d287b1a15a3881f2bff5788bc4bf62c789f2df44d88aae805b54c9a94b8944c0ba798f70062b66160fee312b98879f1dd5d17b33095feb3c5830d28

Và file key.pem

-----BEGIN PUBLIC KEY-----
MFswDQYJKoZIhvcNAQEBBQADSgAwRwJATKIe3jfj1qY7zuX5Eg0JifAUOq6RUwLz
Ruiru4QKcvtW0Uh1KMp1GVt4MmKDiQksTok/pKbJsBFCZugFsS3AjQIDAQAB
-----END PUBLIC KEY-----

Phần lớn thời gian giải bài này mình dùng để đi xử lí cái file key.pem :cry: 
Đọc doc về [PKCS#1 OAEP](https://pycryptodome.readthedocs.io/en/latest/src/cipher/oaep.html)
Đọc lại source code thì trong file `key.pem` lưu cặp public key là $(n,e)$. Để lấy cặp khóa công khai thì ta dùng thư viện `RSA` và `PKCS1_OAEP` của `pycryptodome`. Sau khi có $n$ thì có mình có lên FactorDB để lấy hai thừa số nguyên tố $p,q$. 

from Cryptodome.PublicKey import RSA
from Cryptodome.Cipher import PKCS1_OAEP
from sage.all import factor
from Cryptodome.Util.number import *
ciphertext="249d72cd1d287b1a15a3881f2bff5788bc4bf62c789f2df44d88aae805b54c9a94b8944c0ba798f70062b66160fee312b98879f1dd5d17b33095feb3c5830d28"
enc_flag=bytes.fromhex(ciphertext)
key=RSA.import_key(open('key.pem').read())
n=key.n
e=key.e
p=51894141255108267693828471848483688186015845988173648228318286999011443419469
q=77342270837753916396402614215980760127245056504361515489809293852222206596161
phi=(p-1)*(q-1)
d=inverse(e,phi)
dec_key=RSA.construct((n,e,d,p,q))
cipher=PKCS1_OAEP.new(dec_key)
flag=cipher.decrypt(enc_flag)
print(flag.decode())

## Ron was Wrong, Whit is Right

Source code của bài này:

from Crypto.Cipher import PKCS1_OAEP
from Crypto.PublicKey import RSA


msg = "???"

with open('21.pem') as f:
    key = RSA.importKey(f.read())

cipher = PKCS1_OAEP.new(key)
ciphertext = cipher.encrypt(msg)

with open('21.ciphertext', 'w') as f:
    f.write(ciphertext.hex())


Bài này về cơ bản giống bài trước, trong source có ghi rõ 2 file `21.pem` với `21.ciphertext` thì mình lấy data về rồi làm tương tự.

from Cryptodome.Util.number import *
from Cryptodome.Cipher import PKCS1_OAEP
from Cryptodome.PublicKey import RSA
with open("/home/duc112006/cryptohack/RSA/primes2/ronwhit/keys_and_messages/21.ciphertext",'r') as f:
    ciphertext=f.read().strip()
enc_flag=bytes.fromhex(ciphertext)

key=RSA.import_key(open("/home/duc112006/cryptohack/RSA/primes2/ronwhit/keys_and_messages/21.pem").read())
n=key.n
e=key.e
p=919031168254299342928662994540730760042229248845820491699169870943314884504551963184014786520812939038906152950817942941469675496074887272906954399256046690838233813273902630076899906873722574023918253104149453601408405078374008695616160025877687382663027910687942091698042309812910101246025081363544171351624307177908410700904833438480012985928358897861427063761678614898919524867442676631453135379994570031284289815099294504127712924001149921480778993635917803466637717023744788311275545126346774536416864472035644211758788016642401235014385037912224180351022196262011724157012443048941426178651665266181311662824205620324073087330858064769424755443807165558567191049013947419763315902476674266627953223373671797370373786249718677582213173537848582863398367624397247597103174897140005790273296171101569756006898658668311846034013183862374297777882433967015111727139360441681664840944403450472574336901043555319067050153928231938431298082827397506406624964952344826628463723499263165279281720105570577138817805451223334196017505528543229067732013216932022575286870744622250293712218581458417969597311485156075637589299870500738770767213366940656708757081771498126771190548298648709527029056697749965377697006723247968508680596118923
q=991430390905926023965735525726256769345153760248048478891327804533279477721590201738061124861790305326884541900044434890157058142414306020739922709698601329762087825767461256626800629782378634339618941488765491437487541851308806651586976069659042714378353883168031522106709494592827914376213512564492771821921367377484213072867988877925314809325159382342584541006645302760204539354879391605736604946702073863673524002591877977949645618863730441482821840664748508050205004505250025193611888170440612737112479006348533153568103452396596042639466753099280111709882461562564978070397786887446291916733276692400981917025361391646188802038772976331121474570242334921390569285834250256522656433623912544555266998750630136756355560927237594975904642791712318215315246754105993145827690531584325461597482035600919501967088106457091199733024323755210212616553447076697617349235377466327471959683763796707566328536834402308887105044128592177681553611608618850780128709949316259039664054913946726480968288231015999572777436469163437066403964134928735809253108394078092917006632332098357725950865697047565284013456253933234017983509582245874130968218422573483012858388392588302838940565560162598810462310034964473576147200222580784694005333482381
phi=(p-1)*(q-1)
d=inverse(e,phi)
dec_key=RSA.construct((n,e,d,p,q))
cipher=PKCS1_OAEP.new(dec_key)
flag=cipher.decrypt(enc_flag)
print(flag.decode())

# Padding
## Bespoke Padding
Source code của bài:

#!/usr/bin/env python3

from utils import listener
from Crypto.Util.number import bytes_to_long, getPrime
import random

FLAG = b'crypto{???????????????????????????}'

class Challenge():
def __init__(self):
self.before_input = "Come back as much as you want! You'll never get my flag.\n"
self.p = getPrime(1024)
self.q = getPrime(1024)
self.N = self.p * self.q
self.e = 11

def pad(self, flag):
m = bytes_to_long(flag)
a = random.randint(2, self.N)
b = random.randint(2, self.N)
return (a, b), a*m+b

def encrypt(self, flag):
pad_var, pad_msg = self.pad(flag)
encrypted = (pow(pad_msg, self.e, self.N), self.N)
return pad_var, encrypted

def challenge(self, your_input):
if not 'option' in your_input:
return {"error": "You must send an option to this server"}

elif your_input['option'] == 'get_flag':
pad_var, encrypted = self.encrypt(FLAG)
return {"encrypted_flag": encrypted[0], "modulus": encrypted[1], "padding": pad_var}

else:
return {"error": "Invalid option"}

import builtins; builtins.Challenge = Challenge # hack to enable challenge to be run locally, see https://cryptohack.org/faq/#listener
"""
When you connect, the 'challenge' function will be called on your JSON
input.
"""
listener.start_server(port=13386)

Đọc sơ qua source code ta thấy có một số điểm cần lưu ý như sau:
Khi ta gửi payload `{"option" : "get_flag"}` tới server thì server sẽ trả về các giá trị $a,b,(a\times m +b)^{11}$ và modulo $n$. 

![image](https://hackmd.io/_uploads/ByerHy7do1g.png)

Ta sẽ gửi hai lần để lấy 2 bộ số khác nhau và lấy gcd của chúng để có lại flag 
Code exploit:

from sage.all import *
import sys
def HGCD(a, b):
if 2 * b.degree() <= a.degree() or a.degree() == 1:
return 1, 0, 0, 1
m = a.degree() // 2
a_top, a_bot = a.quo_rem(x^m)
b_top, b_bot = b.quo_rem(x^m)
R00, R01, R10, R11 = HGCD(a_top, b_top)
c = R00 * a + R01 * b
d = R10 * a + R11 * b
q, e = c.quo_rem(d)
d_top, d_bot = d.quo_rem(x^(m // 2))
e_top, e_bot = e.quo_rem(x^(m // 2))
S00, S01, S10, S11 = HGCD(d_top, e_top)
RET00 = S01 * R00 + (S00 - q * S01) * R10
RET01 = S01 * R01 + (S00 - q * S01) * R11
RET10 = S11 * R00 + (S10 - q * S11) * R10
RET11 = S11 * R01 + (S10 - q * S11) * R11
return RET00, RET01, RET10, RET11

def GCD(a, b):
print(a.degree(), b.degree())
q, r = a.quo_rem(b)
if r == 0:
return b
R00, R01, R10, R11 = HGCD(a, b)
c = R00 * a + R01 * b
d = R10 * a + R11 * b
if d == 0:
return c.monic()
q, r = c.quo_rem(d)
if r == 0:
return d
return GCD(d, r)
sys.setrecursionlimit(50000)
N=
p1=...
a1=...
b1=...
p2=...
a2=...
b2=...
P.<x>=PolynomialRing(Zmod(N))
f=(a1*x+b1)^11-p1
g=(a2*x+b2)^11-p2
print(GCD(f,g))

from Cryptodome.Util.number import *
a=12657344838822568851509784228175108576435734294384614625348726284310843959714707634133487770657910655191463620755980459495489494472841767118366311527566239368266347080519905540941177319754836009001361865615932911791937361878909272062189408820287804067583808718375167348246437229018340997505497250048416371314448941176632729935794025594657080086231085613846746664059346363507527557555554476599407486065714754262102441756279472569220118834546301492068101474135392502719581667481534656037586117667379629930998141271085644412479068190285953517013765055181230873772953568052013105018766233570596827529086772321072481811563
b=4042580057131472091314248970803785803073948469522429534465991994624753854632053376850302314624607682069634835520722266510024234730404600400696915519576015482164459213392809088043033286682153420924833795013172825426364798689952787990638864929150971467776104045739032205632634038928769799138244945970441625172537257848511033067397574611668862782721703208024860750318246952182129583948813024596056990345805794037048470742455803123312430321632681399987828646748583596602906337402592935864363220680184089278865521124673568834520998539721998446857492993859139927815027352362987781771544908552672906618984176902863044030427
n=13329181839130552833554997725443499883004895074921614214963769026443408005433731176536630565084987877454566762866250882447016505196099609181864582925418185875025316555731201495213061183763463507154777983053816638762359183262747071468666575258551028413438651667838756861760026939001969118948769300510219971503220073806368290926010984874245492317016068033552659573183987048274118007356411744556272702629475023349100493759818764024291351663054108819125217117484184976057538169893259888924565225318059661883883882455822605555467512386744735681326755140085054174577150109495246225935971790848351213960429677080069426722873
d=(-b*inverse(a,n)) % n
print(long_to_bytes(d))

## Null or Never
Source code:

#!/usr/bin/env python3

from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long

FLAG = b"crypto{???????????????????????????????????}"


def pad100(msg):
    return msg + b'\x00' * (100 - len(msg))


key = RSA.generate(1024, e=3)
n, e = key.n, key.e

m = bytes_to_long(pad100(FLAG))
c = pow(m, e, n)

print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")

File output.txt:

n = 95341235345618011251857577682324351171197688101180707030749869409235726634345899397258784261937590128088284421816891826202978052640992678267974129629670862991769812330793126662251062120518795878693122854189330426777286315442926939843468730196970939951374889986320771714519309125434348512571864406646232154103
e = 3
c = 63476139027102349822147098087901756023488558030079225358836870725611623045683759473454129221778690683914555720975250395929721681009556415292257804239149809875424000027362678341633901036035522299395660255954384685936351041718040558055860508481512479599089561391846007771856837130233678763953257086620228436828

Mấu chốt của bài nằm ở dòng đoạn code

def pad100(msg):
    return msg + b'\x00' * (100 - len(msg))

Trước hết thì ta cần kiểm tra xem thử việc cộng thêm các bytes `b'\x00` vào `msg` thì `msg` sẽ thay đổi như thế nào khi chuyển từ bytes sang long.

Demo:


Và sau khi đệm thêm `b'\x00'` vào


Đầu tiên ta có

't' -> 0x74
'e' -> 0x65
's' -> 0x73
't' -> 0x74
=> bytes_to_long chuyển 0x74657374 dưới dạng hex về 1952805748
Khi ta thêm vào sau \x00 thì chuỗi hex sẽ trở thành 0x7465737400
Các kí tự bị dịch sang trái 2 vị trí nên giá trị của new_text sau khi chuyển sang 
thập phân sẽ gấp 256 = 16*16 lần text

Tới đây thì em nghĩ ngay tới ý tưởng lấy nghiệm của một đa thức nhận `flag` ban đầu là nghiệm bởi vì ta biết được mối quan hệ giữa `msg` và `flag` nên ta có thể viết được đa thức và nghiệm này khá nhỏ so với modulo $n$ nên khả năng cao nó là cái [này](https://doc.sagemath.org/html/en/reference/polynomial_rings/sage/rings/polynomial/polynomial_modn_dense_ntl.html#sage.rings.polynomial.polynomial_modn_dense_ntl.small_roots):

Chuối hơn nữa là bài này không cho ta biết `len(flag)` nên ta phải đi bruteforce.

# Tài liệu tham khảo
Note: Sách về các kiến thức số học sử dụng trong mật mã học https://drive.google.com/file/d/1MeAP73-ZWjRtKkFK-kRfdaUlaNQH4YCa/view