# 20260131_katagaitaiCTF Crypto入門(RSA暗号入門)
## 対象・内容
Cryptoを初めて解く人にむけて、Cryptoで最も出題されるRSAについての説明、実際の問題を通した演習を行います。最後に時間があれば近年の暗号の紹介をします。
## pycryptodome
```
pip3 install pycryptodome
```
## フラグの扱い
情報通信で用いられる現代暗号の多くは情報を数値に変換し、数学的な計算・処理を行うことで暗号化します。
そのためCrypto問でもバイト列として与えられたフラグを、数値に変換して操作することが多いです。
まずは1文字(1byte)の変換を見てみましょう。
pythonではUnicode文字を与えると整数に変換/逆変換する関数として`ord()/chr()`があります。
```python
hex(ord("a")) #hexは10進数を16進数表記へ変換する(str)。
```
```
'0x61' #10進数だと97
```
```python
chr(0x61)
```
```
'a'
```
2文字以上の変換を見てみましょう。
ここでは`pycryptodome`の`bytes_to_long()/long_to_bytes()`を使います。
```python=
from Crypto.Util.number import bytes_to_long
flag = b'flag{katagaitai}'
print(bytes_to_long(flag))
```
```
136143999223211945088441554101120100733
```
```python=
from Crypto.Util.number import long_to_bytes
n = 136143999223211945088441554101120100733
print(long_to_bytes(n))
```
```
b'flag{katagaitai}'
```
:::spoiler 計算方法
例えば`abc`は以下のような計算で数値に変換されます（256進数）。
$$
abc \Leftrightarrow 6382179 = 97\times 256^2 + 98\times 256^1 + 99\times 256^0
$$
:::
### 例題1
10400874617859432610723437734999579042279201 をバイト列に直してください
## 公開鍵暗号
暗号は大きく二つに分類され、暗号化のための鍵と復号のための鍵が同じ暗号を「共通鍵暗号」、異なる暗号を「公開鍵暗号」と呼びます。
今回解説するRSAは「公開鍵暗号」の一種であり、（暗号方式として用いる場合）暗号化のための鍵を公開鍵として公開し、複号のための鍵を秘密鍵として秘密にします。
例えばAlice と Bob が公開鍵暗号を用いて通信を行う際には、それぞれが自身の公開鍵と秘密鍵を作成し、公開鍵のみを公開します。Alice が Bob にメッセージを送る際には Bob の公開鍵を用いて暗号化を行い、Bob は自身の秘密鍵を用いて復号します。第三者 Eve は暗号化に必要な公開鍵を知っていても、暗号文を復号することはできません。
<img src="https://hackmd.io/_uploads/H1joVtW_ke.png" width="500">
## 素因数分解の困難性
RSA暗号は2つの大きな素数を掛け合わせた合成数の、素因数分解の困難性に基づきます。
簡単に言うと、掛け算よりも素因数分解の方がはるかに難しいという数学的な根拠により、 RSA暗号の安全は保たれています。
さらに数値が大きくなればなるほど困難であるため、その指標としてbit長が用いられます。
例）2つの5bit素数の積
5bitの2つの素数の積が713であるとき、その2つの素数を求められるか
↑たった5bitでも難しさは感じてもらえると思います。
`pycryptodome`では`getPrime(bit_length)`で指定したビット数のランダムな素数を生成できます。
```python=
from Crypto.Util.number import getPrime
bit_length = 5
print(getPrime(bit_length))
```
実際に用いられているRSAは少なくとも1024ビット以上の素数が用いられています。
## RSA：鍵生成
RSA暗号では公開鍵$(N,e)$と秘密鍵$d$を用意します。
### 公開鍵
2つの異なる大きな素数$p,q$に対し、
$$ N = p*q $$
を計算します。
$e$は、$\phi(N)$(後述)と互いに素な大きすぎず小さすぎない数として
$$e = 0x10001(65537)$$
がよく使われます。
```python=
bit_length = 1024
p = getPrime(bit_length)
q = getPrime(bit_length)
#m = bytes_to_long(b'flag{katagaitai}')
e = 0x10001
N = p*q
(N,e)
```
### 秘密鍵
$$ d = e^{-1} \mod \phi(N) $$
$d$は法$\phi(N)$のもとで、$e$の逆数です。$\phi(n)$は オイラーのファイ関数と呼ばれるもので、$n$と互いに素である$1$以上$n$以下の自然数の個数と定義されます(素数$p$に対して$\phi(p) = p-1$であることは明らか)。 また、$m,n$が互いに素なとき、$\phi(mn)=\phi(m)\phi(n)$と分解できます。RSA暗号の場合、
$$\phi(N) = \phi(p)\phi(q) = (p-1)(q-1)$$
と計算されます。 そのため、$p$や$q$を知っていれば、$\phi(N)$が求まり、秘密鍵$d$が計算されます。 $N$だけ知っていても、$N$と互いに素である$1$以上$N$以下の自然数を数え上げるのは大変なので$d$は求まりません。(素因数分解も困難なためできない)
```python
phi = (p-1)*(q-1)
d = pow(e,-1,phi)
```
## RSA：暗号化
平文を$m$,暗号文を$c$として、暗号文は
$$c = m^e \mod N$$
と計算されます。
これは($m,e,N$)から$c$を生成するため、公開鍵を知る誰もが計算できます。
```python=
m = bytes_to_long(b"katagaitai")
c = pow(m,e,N)
```
## RSA：復号
復号は
$$m = c^d \mod N$$
と計算されます。
これは($c,d,N$)から$m$を生成するため、秘密鍵を知る者のみが計算できます。
```python
m = pow(c,d,N)
long_to_bytes(int(m))
```
なぜこれで復号できるか、説明します。
その前にオイラーの定理について紹介します。
#### オイラーの定理
:::success
任意の自然数$a,N$に対し、
$$a^{\phi(N)} \equiv 1 \mod N$$
が成り立つ。
証明：https://manabitimes.jp/math/667
:::
$m^{\phi(N)}\equiv 1 \mod N$ ももちろん成り立ちます。
$\mod N$ ではこれを何度かけても値は変わらないので、
$$c^d \equiv m^{ed} \equiv m^{ed+\phi(N)} \equiv m^{ed \mod\phi(N)} \mod N$$
つまり$\phi(N)$は指数部の法とみなせる。
鍵生成の条件から、
$$ed \equiv 1 \mod \phi(N)$$
であるから、
$$c^d \equiv m \mod N$$
RSA.py
```python=
from Crypto.Util.number import getPrime
from Crypto.Util.number import bytes_to_long, long_to_bytes
flag = b"katagaitai-CTF{RSA}" #フラグ
m = bytes_to_long(flag) #フラグを数値に変換
bit_length = 1024
p = getPrime(bit_length)
q = getPrime(bit_length)
N = p*q #公開鍵
e = 0x10001 #公開鍵
phi = (p-1)*(q-1)
d = pow(e,-1,phi) #秘密鍵
c = pow(m,e,N) #暗号化
print(long_to_bytes(c))
k = pow(c,d,N) #復号
print(long_to_bytes(k))
```
### 例題2
以下の情報から暗号文を復号してください
### Output
```
# 秘密鍵
p = 116054663501632195625181997265946681870186375619344559341044638796202099033448320700357180313453778347731232582971763630420453591971248136151766824095086914706957954353181476454551182458909997953921442341886258980880893382702874470454162102298237843418050033854707943370974518156022127441677748697742373585313
q = 111385160791553261456226611755144741360649814106328527492675650067583884066901898238883058036719223629356820222201802223708823054266751543933560580351268100655321960880107094323180192175895957391181669764397313150550195527616862805626171383295318081496975849314054187145182251170344477150143625823633221849517
# 公開鍵
N = 12926767354738909772784065972022895798136088096186071443601140847081921957816567804049648161122491462696383706909539563065735376505373807514890586457861569335237055402799833141747073115385210617902926346195954349016693610609655713466878252786917568131366044284548633036189577149045542000606082578202551321648353209467155489457092211296190801505730640496764568327752662493311536899321468735667657096124623803702551645884282815217970073218318676408101335876579814600960597242052905673574303640974109080419832617992534068740352273334309294518016010373204550751726411197995895937155972420810594326003204341672464247343821
e = 65537
# 暗号文
c = 11824553648834880937304977025852308155067583525060939375830216747877561260624263503479550536298868372228327685288975144863568713784561339526370314025738193706754152832857212297305096362704575169931582070976546251232141440941852915595847875323313360675407463624063750607769698640939633861660676522140579638600688684506964033444764463866892592523014672907014348150822409227828036367104394154497943235154678879564129733994991861286967407652449058407328885071046150622991343853438636380227891195565862127305380935742622038612453042145473210807859394534304026257877106259949189332144123119094159683861115940532955617950069
```
## 演習パート
RSAは現在でも広く用いられている安全な暗号方式であるため、正しく運用されたRSAを解読することはほぼ不可能です。そのためCrypto問では追加の情報が与えられたり、誤った使われ方がされることが多いです。
では実際にCTFの問題を解いてみましょう。
### 演習1 追加パラメータの問題
どうやら$p+q$の値も出力されているようです。
```python=
from Crypto.Util.number import getPrime
from Crypto.Util.number import bytes_to_long
flag = b"katagaitai-CTF{************}"
m = bytes_to_long(flag)
bit_length = 1024
p = getPrime(bit_length)
q = getPrime(bit_length)
N = p*q
e = 0x10001
c = pow(m,e,N)
p_plus_q = p+q
print("N =", N)
print("e =", e)
print("c =", c)
print("p_plus_q =", p_plus_q)
```
### Output
```
N = 22263061029894830691149734442444366775302566156865778880650611060394465378110578182148176735073404853030930448464043823499418179550219223672507057610507526475143642811923703066386890725295114871596777538031346944482953454929745926210029116793042439126417651220339140778539723172057630469733493960583895807787452482607460962027331617710292188740952012237977036136019695116004502194848654022324732627295980045613954609950523324550294591940400392486144664895551277515796018823966652768984462642891225943602167850548225165333306513123229607921105748712159603779489499360019483798159492372530864690769379554933032339715437
e = 65537
c = 22039409403628279202026320397223008973491373096162587076161350840953891709202929050747630002662941581571750146323317247180803925134202212132727492466996879218051833410751528994373680774199082125799907647898285022557426493888543513636065906920762437133260980502878116076862489117701287407406112291776518804305935237858145091715894867766390929211593918254912727855947070942865815082251058092968024793756997304974167647704433963469308824811654872836057656992400970748118172402676647273672324410792202595245701010620629647442627592611465569936060658856606439146476636633502156304101103052563283736249305928099643264890803
p_plus_q = 300382899482728349106478353574960947467016084832173765787035798344765521084105433369198583269409892501669442784690685416706568578130964460423259335223742604547754050838303271216665755783982359854353102996883029138929810234527249282394489016964386416490248946068852813945344105012972916702799930793388058649582
```
:::spoiler ヒント1
二次方程式における解と係数の関係、というものがあります
:::
:::spoiler ヒント2
$$
x^2 - (p+q)x + pq = 0
$$の解はいくつか？
#### 因数分解
$\hspace{100pt}x^2 - (p+q)x + pq = (x-p)(x-q) = 0$ より $p,q$
#### 解の公式
$$\frac{-b\pm \sqrt{b^2-4ac}}{2a}$$
を用いると
$$
\frac{(p+q)\pm \sqrt{(p+q)^2-4pq}}{2}
$$
そのため
$$
p,q = \frac{(p+q)\pm \sqrt{(p+q)^2-4pq}}{2}
$$
:::
:::spoiler solver
```python=
from Crypto.Util.number import long_to_bytes
import math
N = 22263061029894830691149734442444366775302566156865778880650611060394465378110578182148176735073404853030930448464043823499418179550219223672507057610507526475143642811923703066386890725295114871596777538031346944482953454929745926210029116793042439126417651220339140778539723172057630469733493960583895807787452482607460962027331617710292188740952012237977036136019695116004502194848654022324732627295980045613954609950523324550294591940400392486144664895551277515796018823966652768984462642891225943602167850548225165333306513123229607921105748712159603779489499360019483798159492372530864690769379554933032339715437
e = 65537
c = 22039409403628279202026320397223008973491373096162587076161350840953891709202929050747630002662941581571750146323317247180803925134202212132727492466996879218051833410751528994373680774199082125799907647898285022557426493888543513636065906920762437133260980502878116076862489117701287407406112291776518804305935237858145091715894867766390929211593918254912727855947070942865815082251058092968024793756997304974167647704433963469308824811654872836057656992400970748118172402676647273672324410792202595245701010620629647442627592611465569936060658856606439146476636633502156304101103052563283736249305928099643264890803
p_plus_q = 300382899482728349106478353574960947467016084832173765787035798344765521084105433369198583269409892501669442784690685416706568578130964460423259335223742604547754050838303271216665755783982359854353102996883029138929810234527249282394489016964386416490248946068852813945344105012972916702799930793388058649582
A = 1
B = - p_plus_q
C = N
p = (-B + math.isqrt(pow(B,2) - 4 * A * C)) // 2
q = N // p
phi = (p-1)*(q-1)
d = pow(e,-1,phi)
m = pow(c,d,N)
print(long_to_bytes(int(m)))
```
:::
### 演習2 パラメータが悪い問題(q=next_prime\(p\))
pとqが近いと問題はありますか？
```python=
from Crypto.Util.number import getPrime, isPrime
from Crypto.Util.number import bytes_to_long
flag = b"katagaitai-CTF{****************}"
m = bytes_to_long(flag)
def next_prime(n):
while True:
n += 1
if isPrime(n):
return n
bit_length = 1024
p = getPrime(bit_length)
q = next_prime(p)
N = p*q
e = 0x10001
c = pow(m,e,N)
print("N =", N)
print("e =", e)
print("c =", c)
```
### Output
```
N = 14224882908410368764360484874067250400388978460672556891255759017098175256313350112865947942620259550657641892863278357156596163845551071024540508278775724866155378903436287808439690717384226344284098082766014654398833495788216422818786345558009286002776427768249668676948519395474270058331321470694849401101416099242223530653466558703573162382338400582086994992158271180818641679743996809111304540219769071624446246094219874558606679794376050922309695324744971897096923230695728118458370284781138238227312950245661877888897940668689991033328554791631373339072762955787982254713729601813249127066079370331369801505059
e = 65537
c = 14126261345724116189935573765798571201123559396873115386362384916908590205638517186580205445537352471744577267715036213801589914087499465098288392002498627799757398581743975061886396726421376479674451732390972030316611556814920979392928082900749901212629723043432030954781767875829697827744754995253138660953893115046782175857291607288653399091519253705753378669648782331584763778947071794867565964552305882316504605664521710416648017473785556498354177011417859388974666044281992633079667023529901396060617558180817442448043482988748016820412056041051959860175160057152196771273477931436777599522852656969096815641849
```
:::spoiler ヒント
$\sqrt{N}$は$p,q$と非常に近い値になるため、int($\sqrt{N}$)周辺の素数を調べればよいことがわかります。（大きな数値の平方根を求める際にはmath.isqrt(N)を使うとよいです）。
:::
:::spoiler ヒント
:::
:::spoiler solver
```python=
from Crypto.Util.number import long_to_bytes
from Crypto.Util.number import isPrime
import math
N = 14224882908410368764360484874067250400388978460672556891255759017098175256313350112865947942620259550657641892863278357156596163845551071024540508278775724866155378903436287808439690717384226344284098082766014654398833495788216422818786345558009286002776427768249668676948519395474270058331321470694849401101416099242223530653466558703573162382338400582086994992158271180818641679743996809111304540219769071624446246094219874558606679794376050922309695324744971897096923230695728118458370284781138238227312950245661877888897940668689991033328554791631373339072762955787982254713729601813249127066079370331369801505059
e = 65537
c = 14126261345724116189935573765798571201123559396873115386362384916908590205638517186580205445537352471744577267715036213801589914087499465098288392002498627799757398581743975061886396726421376479674451732390972030316611556814920979392928082900749901212629723043432030954781767875829697827744754995253138660953893115046782175857291607288653399091519253705753378669648782331584763778947071794867565964552305882316504605664521710416648017473785556498354177011417859388974666044281992633079667023529901396060617558180817442448043482988748016820412056041051959860175160057152196771273477931436777599522852656969096815641849
def next_prime(n):
while True:
n += 1
if isPrime(n):
return n
q = next_prime(int(math.isqrt(N)))
p=N//q
phi=(p-1)*(q-1)
d=pow(e,-1,phi)
m=pow(c,d,N)
print(long_to_bytes(int(m)))
```
:::
## 補足１：現代の暗号について
現代の暗号は大きく共通鍵暗号と公開鍵暗号に分類され、今回紹介したRSAは公開鍵暗号の一種です。また、公開鍵暗号はその用途によって鍵配送方式と署名方式に分けられ、RSAは主に署名方式として用いられています。
通信で用いるべき安全な暗号方式を知るには、CRYPTRECが公開している推奨暗号リストを確認するのがよいです。
https://www.cryptrec.go.jp/list/cryptrec-ls-0001-2022r1.pdf
## 補足２：今後の暗号について
現在広く用いられている公開鍵暗号(RSAや楕円曲線暗号)は量子コンピュータによって危殆化することが知られており、現在量子コンピュータを使っても解けない(と思われる)暗号「耐量子計算機暗号(PQC)」への移行が進められています。
PQCへの移行デッドラインを正確に予想するのは難しいですが、おおよそ2030年中頃を目標としている国が多いです。（NISTは2035年以降はRSA暗号の使用を禁止予定）
https://nvlpubs.nist.gov/nistpubs/ir/2024/NIST.IR.8547.ipd.pdf
既にKyber(ML-KEM)とDilithium(ML-DSA)と呼ばれる格子暗号などが次世代の暗号として選定され、標準化作業が進められています。CTFにおいても格子暗号、多変数多項式暗号、同種写像暗号を基にした問題が近年数多く見受けられます。
#### 耐量子計算機暗号一例
| | 基にしている数学問題 | 主なPQC |
| ---- | ---- | ---- |
| 格子暗号 | 最短ベクトル問題、LWE問題 | Kyber, Dilithium |
| 多変数多項式暗号 | MQ問題 | UOV, MAYO, QR-UOV |
| 符号暗号 | 線形符号の最短距離復号問題 | HQC, Classic McEliece |
| 同種写像暗号 | 同種写像問題 | SQIsign, (SIKE) |
Sign in with Wallet
Connect another wallet