📖

除数が 2^n の mod平方根を求める(CryptoCTF2022 starter_ecc writeup)

2022/07/17に公開2件

CryptoCTF2022 で出された問題が面白かったのでwriteupを書くことにしました。
難易度としてはmediumで、43 solvesされているので、とてもむずかしい問題、というわけではありませんでしたが学びがありとても好きな問題でした。

問題

問題としては非常にシンプルで、以下のようになっています。
問題は「ECC」となっていますが、解法において、楕円曲線要素はほとんどありません。

#!/usr/bin/env sage

from Crypto.Util.number import *
from secret import n, a, b, x, flag

y = bytes_to_long(flag.encode('utf-8'))

assert y < n
E = EllipticCurve(Zmod(n), [a, b])

try:
        G = E(x, y)
        print(f'x = {x}')
        print(f'a = {a}')
        print(f'b = {b}')
        print(f'n = {n}')
        print('Find the flag :P')
except:
        print('Ooops, ERROR :-(')

解析

楕円曲線暗号の $y$ と $x$ は次の式を満たします。(記号はソースコードのものに対応)

y^2 = x^3 + a x + b \mod n

ここで、 $x$ と $a$ と $b$ が与えられるので、ここから $y$ を求めてくださいという問題になります。

右辺が求まるので、 $\mod n$ 上で平方根を求めるだけですね、簡単～～

それじゃあsagemathの機能を使って求めてみましょう！以下のコードを実行すると…？計算が終わりません。どうやらこれが問題の難しい点のようです。

#!/usr/bin/env sage

from Crypto.Util.number import *

x = 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046477020617917601884853827611232355455223966039590143622792803800879186033924150173912925208583
a = 31337
b = 66826418568487077181425396984743905464189470072466833884636947306507380342362386488703702812673327367379386970252278963682939080502468506452884260534949120967338532068983307061363686987539408216644249718950365322078643067666802845720939111758309026343239779555536517718292754561631504560989926785152983649035
n = 117224988229627436482659673624324558461989737163733991529810987781450160688540001366778824245275287757373389887319739241684244545745583212512813949172078079042775825145312900017512660931667853567060810331541927568102860039898116182248597291899498790518105909390331098630690977858767670061026931938152924839936

print(mod(x^3 + a*x + b, n).sqrt())

解析

通常、楕円曲線暗号に使うあまりの値は素数が使われます。しかし、この $n$ は明らかに偶数で、素数ではありません。素因数分解をしてみましょう。

どうやらfactorDBで素因数分解できる範疇みたいですね。
mod上の平方根といえば、 Tonelli-Shanks algorithm ですね。
Tonelli-Shanks algorithmでは「奇素数」の場合使えるアルゴリズムなので、直感的には 690712633549859897233^6 あたりは計算できそうな気がします。一回 mod 690712633549859897233^6 で計算して平方根が求まるかどうかをチェックしてみましょう。以下のコードを動かすと、実際に求めることができていることが確認できますね。

M = 690712633549859897233^6
print(mod(x^3 + a*x + b, M).sqrt())

# output
# 36236206072093682925062247481413370357729850833651633845213538784805223337120517698394707398791103046274787874369241081809097

651132262883189171676209466993073^5 も同様に求めることができますね。

M = 651132262883189171676209466993073^5
print(mod(x^3 + a*x + b, M).sqrt())

# output
# 23938680681144110126864472369526527114232476444369009413993015648536857120441143070915552032112089272682314228841548237113124931414511899753656778603944647014377036

2^63 はどうやらもとまらないみたいです。

M = 2^63
print(mod(x^3 + a*x + b, M).sqrt())

# output
# too long...

2^63 以外は求まることができたので、2^63を求めると、中国剰余定理で復元することができそうです。

$\mod 2^{63}$ 上での平方根を求める

さて、sagemathに頼っているとどうやらこれを求めることはできなさそうなので、ここの部分は自力で実装していきましょう。

まず、 mod 2^10 などの少ないケースで考えてみると、全探索で求めることができます。

mod = (2**10)
target = (x**3 + a*x + b) % mod

res = []
for j in range(1,mod):
	if pow(j,2,mod) == target:
		res.append(j)

print(res) # [0b10100001, 0b101011111, 0b1010100001, 0b1101011111]

さて、今求めたのは以下の式を満たす $y$ なので、

y^2 \equiv x^3 + a x + b \mod 2^{10}

ここで求まったのは求めるべき答えの「下位10bit」であることがわかります。
では、求めるべき答えの「下位11bit」をここから求めることはできないでしょうか？
やり方としては、下位10bitがわかっているので、上位bitの候補「0と1」を付け足してやれば、合計8通りの答えが出てきて、それらが候補に上がるはずです。(この8個が本当に平方根の全てかどうかは証明してませんすみませんorz)

では、上位bitに0と1をつけて、それを二乗して一致するか確認するコードを書いてみましょう。
どうやら4つ答えが出てきましたね。このまま値を大きくしていって、やがて 2^63 まで到達すると、もともと求めたかった値を求めることができます。

mod = (2**10)
target = (x**3 + a*x + b) % mod

res = []
for j in range(1,mod):
        if pow(j,2,mod) == target:
                res.append(j)

mod = (2**11)
target = (x**3 + a*x + b) % mod
next_candidate = []
for re in res:
    for cand in [re + 2**10, re]:
        if pow(cand,2,mod) == target:
            next_candidate.append(cand)

print(next_candidate) # [1185, 161, 1887, 863]

ここで、本番で書いたコードを掲載します。

#!/usr/bin/env sage
import copy
from Crypto.Util.number import *

x = 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046477020617917601884853827611232355455223966039590143622792803800879186033924150173912925208583
a = 31337
A = 31337
b = 66826418568487077181425396984743905464189470072466833884636947306507380342362386488703702812673327367379386970252278963682939080502468506452884260534949120967338532068983307061363686987539408216644249718950365322078643067666802845720939111758309026343239779555536517718292754561631504560989926785152983649035
# n = 117224988229627436482659673624324558461989737163733991529810987781450160688540001366778824245275287757373389887319739241684244545745583212512813949172078079042775825145312900017512660931667853567060810331541927568102860039898116182248597291899498790518105909390331098630690977858767670061026931938152924839936
n = 2**63 * 690712633549859897233**6 * 651132262883189171676209466993073**5
assert n == 117224988229627436482659673624324558461989737163733991529810987781450160688540001366778824245275287757373389887319739241684244545745583212512813949172078079042775825145312900017512660931667853567060810331541927568102860039898116182248597291899498790518105909390331098630690977858767670061026931938152924839936
print((x**3 + a*x + b) % 2**63)

ans = [[],]

for i in range(1,21):
        mod = (2**i)
        target = (x**3 + a*x + b) % mod

        res = []
        for j in range(1,2**i):
                if (j**2)%mod == target:
                        res.append(j)

        ans.append(res)

# checker
# i = 0
# for an in ans:
#       print("--------------------------------------------------")
#       mod = (2**i)
#       nexts = []
#       print("mod: ", mod)
#
#       nexts = set()
#       for a in an:
#               print(a)
#               nexts.add(a)
#               nexts.add(-a%mod)
#               nexts.add(a+2**i)
#               nexts.add((-a%mod)+2**i)
#
#       next_mod = (2**(i+1))
#       next_target = (x**3 + A*x + b) % next_mod
#       next_ans = []
#       for next in nexts:
#               if next*next % next_mod == next_target:
#                       next_ans.append(next)
#
#       print(next_ans)
#       i += 1

an = ans[-1]
i = 20
while i < 63:
        mod = (2**i)
        nexts = []

        nexts = set()
        for a in an:
                nexts.add(a)
                nexts.add(-a%mod)
                nexts.add(a+2**i)
                nexts.add((-a%mod)+2**i)

        print(i+1)
        next_mod = (2**(i+1))
        next_target = (x**3 + A*x + b) % next_mod
        next_ans = []
        for next in nexts:
                if (next*next) % next_mod == next_target:
                        next_ans.append(next)

        an = next_ans
        i += 1

for ans in next_ans:
        assert (ans*ans) % 2**63 == (x**3 + A*x + b) % 2**63

print(next_ans)

中国剰余定理で復元する

さあ、ここでボトルネックになっていた $mod 2^{63}$ を求めることができたので、あとは中国剰余定理で復元するだけです。ここで、気をつけなければならないことは、平方根の候補は複数あるので、すべて列挙する必要があることです。それに気をつけて、以下のようなコードを書きました。

#!/usr/bin/env sage

from Crypto.Util.number import *

x = 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046477020617917601884853827611232355455223966039590143622792803800879186033924150173912925208583
a = 31337
b = 66826418568487077181425396984743905464189470072466833884636947306507380342362386488703702812673327367379386970252278963682939080502468506452884260534949120967338532068983307061363686987539408216644249718950365322078643067666802845720939111758309026343239779555536517718292754561631504560989926785152983649035
# n = 117224988229627436482659673624324558461989737163733991529810987781450160688540001366778824245275287757373389887319739241684244545745583212512813949172078079042775825145312900017512660931667853567060810331541927568102860039898116182248597291899498790518105909390331098630690977858767670061026931938152924839936
n = 2^63 * 690712633549859897233^6 * 651132262883189171676209466993073^5
assert n == 117224988229627436482659673624324558461989737163733991529810987781450160688540001366778824245275287757373389887319739241684244545745583212512813949172078079042775825145312900017512660931667853567060810331541927568102860039898116182248597291899498790518105909390331098630690977858767670061026931938152924839936


# y = bytes_to_long(flag.encode('utf-8'))

[2351055617237491873, 6962741635664879777, 6872316419617283935, 2260630401189896031]

E = EllipticCurve(Zmod(n), [a, b])

mo = 1
fs = [
        690712633549859897233^6,
        651132262883189171676209466993073^5,
]

vals = []

for fac in fs:
        vals.append(mod(x^3 + a*x + b, fac).sqrt(all=True))

fs.append(2^63)
vals.append([2351055617237491873, 6962741635664879777, 6872316419617283935, 2260630401189896031])
for i in range(2):
        for j in range(2):
                for k in range(4):
                        memo = [int(vals[0][i]), int(vals[1][j]), int(vals[2][k])]
                        print(long_to_bytes(int(crt(memo, fs))))