WaniCTF'21-spring
WaniCTF、楽しかったです。
Crypto問のwrite-upです。どなたかの参考になるといいな。
問題はこちら -> WaniCTF
Simple conversion
2つのファイルが与えられます。
convert.py
from const import flag
def bytes_to_integer(x: bytes) -> int:
x = int.from_bytes(x, byteorder="big")
return x
print(bytes_to_integer(flag))
output.txt
709088550902439876921359662969011490817828244100611994507393920171782905026859712405088781429996152122943882490614543229
解き方はこんな感じ。
solver.py
from Crypto.Util.number import long_to_bytes
out = 709088550902439876921359662969011490817828244100611994507393920171782905026859712405088781429996152122943882490614543229
print(long_to_bytes(out))
# b'FLAG{7h1s_i5_h0w_we_c0nvert_m3ss@ges_1nt0_num63rs}'
初めてCryptoに取り組む人は、pycryptodomeがおすすめです。
chr()とかint().to_bytes()とかbinasciiでも解けると思う。
ASCIIの知識を持っているとよい。wikipedia
Easy
encrypt.pyを読むと、フラグの文字を数字に変換して、未知の定数a,bで変換しています。古典暗号のアフィン暗号っぽいですね。
encrypt.py
with open("flag.txt") as f:
flag = f.read().strip()
A = REDACTED
B = REDACTED
plaintext_space = "ABCDEFGHIJKLMNOPQRSTUVWXYZ_{}"
assert all(x in plaintext_space for x in flag)
def encrypt(plaintext: str, a: int, b: int) -> str:
ciphertext = ""
for x in plaintext:
if "A" <= x <= "Z":
x = ord(x) - ord("A")
x = (a * x + b) % 26
x = chr(x + ord("A"))
ciphertext += x
return ciphertext
if __name__ == "__main__":
ciphertext = encrypt(flag, a=A, b=B)
print(ciphertext)
output.txt
HLIM{OCLSAQCZASPYFZASRILLCVMC}
使用したコードは以下のとおり。使っている関数はencrypt.pyのやつ、そのままです。aとbの値が不明なのでここは総当たりして、先頭の4文字が「FLAG」になるものを探しました。よくわかってないまま解いてしまいましたが、アフィン暗号って暗号化と同じ関数（ただしパラメータa,bは違う）で解けるものなんでしょうか。
solver.py
out = "HLIM{OCLSAQCZASPYFZASRILLCVMC}"
def encrypt(plaintext: str, a: int, b: int) -> str:
ciphertext = ""
for x in plaintext:
if "A" <= x <= "Z":
x = ord(x) - ord("A")
x = (a * x + b) % 26
x = chr(x + ord("A"))
ciphertext += x
return ciphertext
for A in range(30):
for B in range(30):
ciphertext = encrypt(out, a=A, b=B)
if ciphertext[:4] == "FLAG":
print(ciphertext)
# FLAG{WELCOMETOCRYPTOCHALLENGE}
Can't restore the flag?
nc(netcat)コマンドが必要な問題。
nc crt.cry.wanictf.org 50000
server.py
from Crypto.Util.number import bytes_to_long
with open("flag.txt", "rb") as f:
flag = f.read()
flag = bytes_to_long(flag)
assert flag <= 10 ** 103
upper_bound = 300
while True:
try:
mod = int(input("Mod > "))
if mod > upper_bound:
print("Don't cheat 🤪")
continue
result = flag % mod
print(result)
except Exception:
print("Bye 👋")
break
ncで接続してみるとこんな感じ。
user:~$ nc crt.cry.wanictf.org 50000
Mod > 2
0
Mod > 3
2
Mod > 17
8
Mod > 300
290
Mod > 301
Don't cheat 🤪
Mod >
Bye 👋
サーバーではフラグが数字に変換されていて、ユーザが入力した数字で割った余りが返されるようになってるみたい。
上で試した結果を見ると、フラグは2で割ると0、3で割ると2、17で割ると8、となるような数字であることがわかる。ただし、最大で300までしか入力できない。
解法ですが、この問題では中国剰余定理（CRT）を使います。
考え方は 「中国剰余定理 (CRT) の解説と、それを用いる問題のまとめ」を参考にしています。
コードは3つに分けて記載します。
- 素数の集合を求める（SageMath）
- サーバーに問い合わせ（Python）
- 中国剰余定理（SageMath）
（なんで分けたかというと、SageMathCellでsocketが動かなかったため）
まず、300以下の素数の集合を求めます。
楽をするためにSageMathを頼ります。インストールしていなくても、SageMathCellというものがあるので（制限はあるけど）簡単に試せます。
get_primes.sage
ps = []
i = 0
while True:
p = Primes()[i] # 素数の集合から順番にとってくる
if p <= 300:
ps.append(p)
else:
break
i += 1
print(ps)
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293]
300までの素数の集合が得られました。
次はサーバーに問い合わせ。（ここはSageMathなし）
socketの使い方はここがわかりやすいです。
nc_server.py
import socket
adress = "crt.cry.wanictf.org"
port = 50000
def nc(address,port,ps):
data = {}
with socket.socket(socket.AF_INET, socket.SOCK_STREAM) as s:
s.connect((address, port))
k = 0
p = b""
while ps[k] < 300:
r = s.recv(1024)
# print(p, r.split()[0])
if r.split()[0] != b"Mod":
data[ps[k]] = int(r.split()[0])
if ps[k] == ps[-1]:
break
k += 1
if r.split()[-1] == b">":
p = str(ps[k]).encode()
s.sendall(p + b"\n")
return data
ps = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293]
# ps = Primes() # ローカルでSageMathが使えるならこれで良い
data = nc(adress,port,ps)
print(data)
# {2: 0, 3: 2, 5: 0, 7: 2, 11: 10, 13: 7, 17: 8, 19: 10, 23: 17, 29: 17, 31: 24, 37: 7, 41: 31, 43: 30, 47: 18, 53: 43, 59: 2, 61: 31, 67: 44, 71: 14, 73: 1, 79: 50, 83: 67, 89: 48, 97: 21, 101: 54, 103: 47, 107: 105, 109: 80, 113: 43, 127: 103, 131: 74, 137: 104, 139: 83, 149: 56, 151: 140, 157: 148, 163: 13, 167: 154, 173: 96, 179: 76, 181: 162, 191: 49, 193: 43, 197: 182, 199: 168, 211: 73, 223: 49, 227: 158, 229: 39, 233: 95, 239: 40, 241: 189, 251: 206, 257: 245, 263: 242, 269: 205, 271: 67, 277: 89, 281: 0, 283: 282, 293: 222}
ここの出力は辞書型で、{素数: 素数でフラグを割った余り}となってます。
最後にSageMathで中国剰余定理を使います。
rep_crt.sage
import binascii
ps = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293]
data = {2: 0, 3: 2, 5: 0, 7: 2, 11: 10, 13: 7, 17: 8, 19: 10, 23: 17, 29: 17, 31: 24, 37: 7, 41: 31, 43: 30, 47: 18, 53: 43, 59: 2, 61: 31, 67: 44, 71: 14, 73: 1, 79: 50, 83: 67, 89: 48, 97: 21, 101: 54, 103: 47, 107: 105, 109: 80, 113: 43, 127: 103, 131: 74, 137: 104, 139: 83, 149: 56, 151: 140, 157: 148, 163: 13, 167: 154, 173: 96, 179: 76, 181: 162, 191: 49, 193: 43, 197: 182, 199: 168, 211: 73, 223: 49, 227: 158, 229: 39, 233: 95, 239: 40, 241: 189, 251: 206, 257: 245, 263: 242, 269: 205, 271: 67, 277: 89, 281: 0, 283: 282, 293: 222}
x = crt(data[ps[0]],data[ps[1]],ps[0],ps[1])
pp = ps[0]*ps[1]
for i in range(2,len(data)):
x = crt(data[ps[i]],x,ps[i],pp)
pp = ps[i]*pp
print(binascii.a2b_hex(hex(x)[2:]))
# b'FLAG{Ch1n3s3_r3m@1nd3r_7h30r3m__so_u5eful}\n'
ちょいちょいSageMathを頼ってますが、素数の生成も中国剰余定理も自分で実装したほうが力はつくと思う。
Extra
CTFでおなじみのRSAです。
encrypt.py
from Crypto.Util.number import getPrime, bytes_to_long
with open("flag.txt", "rb") as f:
flag = f.read()
p, q = getPrime(1024), getPrime(1024)
N = p * q
M = 2 * p + q
e = 0x10001
def encrypt(plaintext: bytes) -> int:
plaintext = bytes_to_long(plaintext)
c = pow(plaintext, e, N)
return c
if __name__ == "__main__":
c = encrypt(flag)
print(f"{N = }")
print(f"{M = }")
print(f"{e = }")
print(f"{c = }")
output.txt
N = 22255382023772668851018179427844169178508638456713544208965498667359965716247243217931028270320680101854437928939452335472153643094266035953797432826168426002458800906764442624308120284177094975740468163835305872963635678413995878812492729432260346481442092245748885202467992527408086207041964831622724073720751839241897580988210971776031098476500998975223039782371635291859483569580516707907602619018780393060215756966917504096971372578145138070121288608502379649804953835336933545368863853793291348412017384228807171466141787383764812064465152885522264261710104646819565161405416285530129398700414912821358924882993
M = 455054308184393892678058040417894434538147052966484655368629806848690951585316383741818991249942897131402174931069148907410409095241197004639436085265522674198117934494409967755516107042868190564732371162423204135770802585390754508661199283919569348449653439331457503898545517122035939648918370853985174413495
e = 65537
c = 17228720052381175899005296327529228647857019551986416863927209013417483505116054978735086007753554984554590706212543316457002993598203960172630351581308428981923248377333772786232057445880572046104706039330059467410587857287022959518047526287362946817619717880614820138792149370198936936857422116461146587380005750298216662907558653796277806259062461884502203484610534512552197338982682870358910558302016481352035443274153409114492025483995668048818103066011831955626539382173160900595378864729936791103356604330731386911513668727994911216530875480647283550078311836214338646991447576725034118526046292574067040720093
RSA暗号の説明は省略します。
普通のRSAと異なる点は、$M = 2p + q$が与えられていることですね。これが手掛かりになっていそうです。
私はこんな感じで変形しました。
$$ M^2 - 8N = (2p + q)^2 - 8pq = 4p^2 -4pq + q^2 = (2p - q)^2$$
なので、
$$ M + (M^2 - 8N)^{1/2} = (2p+q) + (2p-q) = 4p$$
から、$p$が得られました。 以上の式をそのままコードにします。
solver.sage
import binascii
N = 22255382023772668851018179427844169178508638456713544208965498667359965716247243217931028270320680101854437928939452335472153643094266035953797432826168426002458800906764442624308120284177094975740468163835305872963635678413995878812492729432260346481442092245748885202467992527408086207041964831622724073720751839241897580988210971776031098476500998975223039782371635291859483569580516707907602619018780393060215756966917504096971372578145138070121288608502379649804953835336933545368863853793291348412017384228807171466141787383764812064465152885522264261710104646819565161405416285530129398700414912821358924882993
M = 455054308184393892678058040417894434538147052966484655368629806848690951585316383741818991249942897131402174931069148907410409095241197004639436085265522674198117934494409967755516107042868190564732371162423204135770802585390754508661199283919569348449653439331457503898545517122035939648918370853985174413495
e = 65537
c = 17228720052381175899005296327529228647857019551986416863927209013417483505116054978735086007753554984554590706212543316457002993598203960172630351581308428981923248377333772786232057445880572046104706039330059467410587857287022959518047526287362946817619717880614820138792149370198936936857422116461146587380005750298216662907558653796277806259062461884502203484610534512552197338982682870358910558302016481352035443274153409114492025483995668048818103066011831955626539382173160900595378864729936791103356604330731386911513668727994911216530875480647283550078311836214338646991447576725034118526046292574067040720093
pp = M**2 - 8*N
p2_q = pp**(1/2) # pythonだと、OverflowError: int too large to convert to float
p = (M + p2_q) / 4
q = N/p
assert(N == p*q) # 因数分解できてる！
# ここからは通常のRSA
phi = (p-1)*(q-1)
d = pow(e,-1,phi) # 秘密鍵（復号鍵）dを求める
m = pow(c,d,N) # 復号
print(binascii.a2b_hex(hex(m)[2:]))
b' FLAG{@n_ex7ra_param3ter_ru1n5_3very7h1n9}\n'
pythonで実行すると途中でエラーが出たのですが、SageMathだと普通に動くようです。
OUCS
準同型暗号（Homomorphic Encryption）の問題です。準同型の説明はWikipediaやherumiさんの記事をご覧ください。
準同型暗号には色々種類があるのですが、今回はOkamoto Uchiyama CryptoSystemが使われているみたいです。問題のコードは省略しますが、Wikipediaの通りに実装されていそうです。
ncコマンドでサーバーにアクセスすると、フラグの暗号文が得られたり、自分で入力したデータの暗号化・復号ができるようになっています。（ただし、フラグの暗号文は復号できないようになってる）
実際に準同型性を確かめてみましょう。
例えば、数字の2と3を暗号化してみます。
user:~$ nc oucs.cry.wanictf.org 50010
.oooooo. ooooo ooo .oooooo. .oooooo..o
d8P' `Y8b `888' `8' d8P' `Y8b d8P' `Y8
888 888 888 8 888 Y88bo.
888 888 888 8 888 `"Y8888o.
888 888 888 8 888 `"Y88b
`88b d88' `88. .8' `88b ooo oo .d8P
`Y8bood8P' `YbodP' `Y8bood8P' 8""88888P''
╭─────────────────────╮
│ 1. Encrypt flag │
│ 2. Encrypt │
│ 3. Decrypt │
│ 4. Show public key │
│ 5. Exit │
╰─────────────────────╯
> 2
Enter your plaintext
> 2
ciphertext = 0x168098ac58793f99b23f9d2299a53e7c852cfc903c31d3e61e60936ebba4f7d69b1b13ee10c5baddd2d8e441f4c7aaeb0a8c71b07e2ba1de2020e28757adf06c740519de5c16b0fc7a7130873e1a1b790c209a477a81ce4dbde0edd8f8e15ab13ece76ddeebd14cce130d799fe19ce6465cf6df76d648a7e8975c90203f23e0b23fa2fc3405e06962ccb5c1f1b48f0e80f439f13a813643c818e96fc83069b6d4ff3c7ec22175ba5cd7f45ce2e31d8061fdcc3462f4fea8734a434f3ae95f60077140ea3833257ffadfd7dc05943775045aca370fd182d035c2cf7386ec4cb900c39724fef9a1d67bf3a4e22c24f3947a54df4d5e3c74bc38053b25d111f4e721011b9c28d1fd73ae26907cbfeed40a7d19d9d778f8fc7064c95d550110eaa1fdd826c55745f89c53421e6cc5463cc1a562d3342699570e3f54ed382ce2cecba6598a9cf73d54975ff64075a4e5941482d81b4442b470ec5c9668f71231e7e9002be39434aed25479f1d02827c7b77a402971fcc86dcf021e8a9e285fd7325f7
╭─────────────────────╮
│ 1. Encrypt flag │
│ 2. Encrypt │
│ 3. Decrypt │
│ 4. Show public key │
│ 5. Exit │
╰─────────────────────╯
> 2
Enter your plaintext
> 3
ciphertext = 0x1ee2bed2789efc8212a56c1864f4dcc4d1474c726053336ad5bfcd3d6567f4a1d025446c28c64f927de86c0b842721daf48f4861ceec47d81bdabb38607716d020f54d85eb08eb499c4874207f8f78d1ee4a1007807fc3fd7b38452f6c3258306c0089f569d4ead5a140e01d02ba1eef3b15bbbbb44797c89ca03562f67b261cbb49d9fe6ae9a5f5b8ea73eaa5b2b65a216b929e755e6f80afc0432cae100ed40fe2d0a842eb6e65ac891862e46df55eb0c75fc0a41f57bb33083e665dd8887f06228e10c496b36d15068aed83c949d0c32ce77a427cbdfeabfd470bc0cb3fae2282ca23687200be4e6d643ef6c6efb6286fd1908e04a1c06b39c4c58530d78a0b421b2718c16bc8e27b3b1da9e6ae95db226e6719980041194c16b4c44c11dc0d88f6116122df02c53e15d6a4bf25708f3fd63a09b376dc85692c531c2beab862e48496ad8005d74a6ef6b15f05839efe6d7abe506babed3ecf1ddbfc6c74bf7a00f016c162e567e89b4ab53bcb44cd044ec6d8528ce9838f45814a309ab17c
2つの暗号文が得られました。次に暗号文の積をとって、
# 2のciphertext
c1 = 0x168098ac58793f99b23f9d2299a53e7c852cfc903c31d3e61e60936ebba4f7d69b1b13ee10c5baddd2d8e441f4c7aaeb0a8c71b07e2ba1de2020e28757adf06c740519de5c16b0fc7a7130873e1a1b790c209a477a81ce4dbde0edd8f8e15ab13ece76ddeebd14cce130d799fe19ce6465cf6df76d648a7e8975c90203f23e0b23fa2fc3405e06962ccb5c1f1b48f0e80f439f13a813643c818e96fc83069b6d4ff3c7ec22175ba5cd7f45ce2e31d8061fdcc3462f4fea8734a434f3ae95f60077140ea3833257ffadfd7dc05943775045aca370fd182d035c2cf7386ec4cb900c39724fef9a1d67bf3a4e22c24f3947a54df4d5e3c74bc38053b25d111f4e721011b9c28d1fd73ae26907cbfeed40a7d19d9d778f8fc7064c95d550110eaa1fdd826c55745f89c53421e6cc5463cc1a562d3342699570e3f54ed382ce2cecba6598a9cf73d54975ff64075a4e5941482d81b4442b470ec5c9668f71231e7e9002be39434aed25479f1d02827c7b77a402971fcc86dcf021e8a9e285fd7325f7
# 3のciphertext
c2 = 0x1ee2bed2789efc8212a56c1864f4dcc4d1474c726053336ad5bfcd3d6567f4a1d025446c28c64f927de86c0b842721daf48f4861ceec47d81bdabb38607716d020f54d85eb08eb499c4874207f8f78d1ee4a1007807fc3fd7b38452f6c3258306c0089f569d4ead5a140e01d02ba1eef3b15bbbbb44797c89ca03562f67b261cbb49d9fe6ae9a5f5b8ea73eaa5b2b65a216b929e755e6f80afc0432cae100ed40fe2d0a842eb6e65ac891862e46df55eb0c75fc0a41f57bb33083e665dd8887f06228e10c496b36d15068aed83c949d0c32ce77a427cbdfeabfd470bc0cb3fae2282ca23687200be4e6d643ef6c6efb6286fd1908e04a1c06b39c4c58530d78a0b421b2718c16bc8e27b3b1da9e6ae95db226e6719980041194c16b4c44c11dc0d88f6116122df02c53e15d6a4bf25708f3fd63a09b376dc85692c531c2beab862e48496ad8005d74a6ef6b15f05839efe6d7abe506babed3ecf1ddbfc6c74bf7a00f016c162e567e89b4ab53bcb44cd044ec6d8528ce9838f45814a309ab17c
# 暗号文の積を求める
print(hex(c1*c2))
# 0x2b70030ebebb8a9c24f4352b49755c3ab7fc378407e8228044bcbee0a00f6d865fbfe2ad18047dc177c957c637f75d22440f9cbbcd901b7697c3942157dc9138f1122a2c911ab67dc2f3acb77045f5aa72a2d034e9fa6f81f5d47fe607c51b80087ba9249d57d26a9e5893751a559c4db5c6749265232a068a3d483d6219c0f2ac58c2b84930babd281281d4011cbd06cb17ca718c4b6edcf82e5005049823f40437d2e2102a70b64f1fb874c5c0d09bbc46af7694abe646ad87502919e561f33335d13c9f8f1978c923156202669e15f7c51387d82e06f91a17c9003873fb481cba4c0d6f0c08fa008a7b0fd1de0f62924ba3b9f26389e7b2882b10e2e901afc270417204639a9dcab1d33f4fa0601da4fde38f144814bfbe20e477b7ba488d92f5a99753a4ffa1e25f4aa7b9ce4b4e8c5611c845d9700feda79f39e415e709a7b131e5e10bd449c1d8777838405e432dcc7a61cddd6043fe396db5dcc3fe4b40fd407b247c7df5c8bf734beee9f0e5c7dd2f68879d3070a6c202c20f1c56523a64e7a67b6dc398ffb4ea0cfd2bdcb7923d01f0c03d46dd7179532526637290a8623faa1779c5ed370df653d447ea7cc9b53e58f6d172737e4c2854acdfcdd948a8c5000badf626364f6e812952f9f43a1cc20063c03e5e6dc4b71a64abd3867c2879b00a80e4e8fdfdc5c09a8418e902d212beb71d31d13fa1eb886e5a07f13927195648708222d5c4fb6710aa50ac70649f4bf0f4f2b4e2e4c2094b05e0c3db6f0822756c2dcd29e505b59c1c6a4a22dc62d20b9ec729338ca5f622763e2546fed0b5b5dd5ec92e15ce15bc30f889c4f27f5476afaae6f08644abe4e03c15f29ae6deabddb2add06bf3cb396b13783d79b123f26bbbe617f7d961d5b0c0c93f0712f339f984de358963f8cd06e178c7b27128a85693e3ffca2b1fee690934d2fe853b4d7be21c0c7fcca5e09740724490ada598fed1739a1c209dc234510ad482b1c7b53f456eb74965816be02fffbab00e1d20a4bf967aa1bb81c57d20653711a121c837c9e907fe283c802740003d2e7650891710b0a05dbec879c2aa4
この積の値を復号してみます。
╭─────────────────────╮
│ 1. Encrypt flag │
│ 2. Encrypt │
│ 3. Decrypt │
│ 4. Show public key │
│ 5. Exit │
╰─────────────────────╯
> 3
Enter your ciphertext
> 0x2b70030ebebb8a9c24f4352b49755c3ab7fc378407e8228044bcbee0a00f6d865fbfe2ad18047dc177c957c637f75d22440f9cbbcd901b7697c3942157dc9138f1122a2c911ab67dc2f3acb77045f5aa72a2d034e9fa6f81f5d47fe607c51b80087ba9249d57d26a9e5893751a559c4db5c6749265232a068a3d483d6219c0f2ac58c2b84930babd281281d4011cbd06cb17ca718c4b6edcf82e5005049823f40437d2e2102a70b64f1fb874c5c0d09bbc46af7694abe646ad87502919e561f33335d13c9f8f1978c923156202669e15f7c51387d82e06f91a17c9003873fb481cba4c0d6f0c08fa008a7b0fd1de0f62924ba3b9f26389e7b2882b10e2e901afc270417204639a9dcab1d33f4fa0601da4fde38f144814bfbe20e477b7ba488d92f5a99753a4ffa1e25f4aa7b9ce4b4e8c5611c845d9700feda79f39e415e709a7b131e5e10bd449c1d8777838405e432dcc7a61cddd6043fe396db5dcc3fe4b40fd407b247c7df5c8bf734beee9f0e5c7dd2f68879d3070a6c202c20f1c56523a64e7a67b6dc398ffb4ea0cfd2bdcb7923d01f0c03d46dd7179532526637290a8623faa1779c5ed370df653d447ea7cc9b53e58f6d172737e4c2854acdfcdd948a8c5000badf626364f6e812952f9f43a1cc20063c03e5e6dc4b71a64abd3867c2879b00a80e4e8fdfdc5c09a8418e902d212beb71d31d13fa1eb886e5a07f13927195648708222d5c4fb6710aa50ac70649f4bf0f4f2b4e2e4c2094b05e0c3db6f0822756c2dcd29e505b59c1c6a4a22dc62d20b9ec729338ca5f622763e2546fed0b5b5dd5ec92e15ce15bc30f889c4f27f5476afaae6f08644abe4e03c15f29ae6deabddb2add06bf3cb396b13783d79b123f26bbbe617f7d961d5b0c0c93f0712f339f984de358963f8cd06e178c7b27128a85693e3ffca2b1fee690934d2fe853b4d7be21c0c7fcca5e09740724490ada598fed1739a1c209dc234510ad482b1c7b53f456eb74965816be02fffbab00e1d20a4bf967aa1bb81c57d20653711a121c837c9e907fe283c802740003d2e7650891710b0a05dbec879c2aa4
plaintext = 0x5
すると、数字の5が得られました。この結果から、暗号文の積は平文の和になることが予想できます。（予想で進めていますが、コードをしっかり読めばわかるはず...）
式で表すとこんなイメージ。
$$ Dec(Enc(2) \cdot Enc(3)) = 2+3 $$
そこで、フラグの暗号文に、先ほど使用した3の暗号文を乗算して、
# 3のciphertext
c2 = 0x1ee2bed2789efc8212a56c1864f4dcc4d1474c726053336ad5bfcd3d6567f4a1d025446c28c64f927de86c0b842721daf48f4861ceec47d81bdabb38607716d020f54d85eb08eb499c4874207f8f78d1ee4a1007807fc3fd7b38452f6c3258306c0089f569d4ead5a140e01d02ba1eef3b15bbbbb44797c89ca03562f67b261cbb49d9fe6ae9a5f5b8ea73eaa5b2b65a216b929e755e6f80afc0432cae100ed40fe2d0a842eb6e65ac891862e46df55eb0c75fc0a41f57bb33083e665dd8887f06228e10c496b36d15068aed83c949d0c32ce77a427cbdfeabfd470bc0cb3fae2282ca23687200be4e6d643ef6c6efb6286fd1908e04a1c06b39c4c58530d78a0b421b2718c16bc8e27b3b1da9e6ae95db226e6719980041194c16b4c44c11dc0d88f6116122df02c53e15d6a4bf25708f3fd63a09b376dc85692c531c2beab862e48496ad8005d74a6ef6b15f05839efe6d7abe506babed3ecf1ddbfc6c74bf7a00f016c162e567e89b4ab53bcb44cd044ec6d8528ce9838f45814a309ab17c
# フラグの暗号文
c_flag = 0x27c55e00b7f98342920a466b870e441b59b3e3ce5e46ad39f8a7636b62031ba5d47dc6376282c10f3b4a0001bf148c29c1bcfd67cb7dba1d4b514d9d86a3759ce786cb5f5aee2d856bc8cf842378c36d845609fc4d1276719bb54fae2867b12ffa1eb43b30e0c39214f057726f4aee9fc06da0cceffa2925f388b79d89df5604a55e6f9836ef71d5e422a813f4aaa8472b75a536d7d43f0bf4c0b09f24011df09deff4ef9c504cf98e0f84df1e77130120920ede7d5c09ecca8704dd5e326852c22346723a14cc3d0020f07e3f7fd6ff11c614918094721565f79dae244e160cbc9c1bed7defda6e6aad3fa385ac5769fb7895949796d6ff26c778152d3429659918f093ac7aa750299522294392b64d80804c63140824f40d99742828f9ebf1220571000ede7f787d313e155adef23a28ceddfeed66220ad786d2a5a12a1a316b1df60160e0490ab6fa9ae8be004c0b0e8d2ccde662c59b21d27c5dee6cfc6289179a49345440d4ffa811d38bb9ea3ba3571db5b89cab34ae002a93bbd75f76
print(hex(c_flag*c2))
# 0x4cc5ae6409a83e4a051bcec2425fbcbb503f153420d694b284cceab1e57ba9044e29a0321831dd6905b64b819bdf544e2e8138f2f75b527370cc7a99526259a57a5aeeb89544342c6e24fbfabddabd14c6aebedf1f288879a886a6fcc216589bc7c1f5434a9754d44e5cf46b00941416785b849d471a6759daeeba850ea4b71a467995bd4d9eb9dfaa65efde84a31fe127157d259d7946f106042368caf61c9944ec0a544485c23a2ec1439847332641c4be1a6473a3f0c940f975c09f234c5ca2b05cc237861954e95da6aab56b9b58484a991e9affcd8331a4f4d677ad6d2a0a7e64b959c89ea08908c8241de217dcb7eabcdb98bde16b33352c741b790169001846c13144079d4c5ab5d7c6aef4b82a4a367996cf1517c0cc5ac11483fcc64cdef6435f132c939b4eb0093b1a54305df9d5be34d42bba1ca8a23c88aef08e1ffd3b78ad35c726ce1d559a3c24654b6205b63884406ade9f11841ba674301aa9e79f43ad1007cfdc0f4eda864d1db437ea7a29f3c084d647673b41fbbe2fbf9b5afa06700876b80374f75faefdc496a01032c85acf5d431e36b5e6a14171b86708e389c37b424f07c02d16301f509c5c48e44c14efa8db9c18859148d46df43219fb2bf8c53a4e57a538270559461f34e4dae965b28f07965fa8a24605de7168745a9cc4197bb6bfa1b1dd377481ac0617d1372fae2d1506dc1c209ba6b26c7f9b393b8981795581cf3f8d08c4dfd3eeaeb38b81e15b6974c3261761353f05b0b60d55272feb080f3bf912bd97d8b2df92a36a6b0a698f37e0bcdbe70ad5048bc26ad48f532df830fb08f1dfff2f31a6f52ded87947739459bc3be0c3398e083711a0f9a223bd6dc0ca5abf9a7b6c5c218ed20f70ad2f145d9cd29cbcee63c2b62a117392e6c0d666f589c3e5ab585293a430de3bb4ec6a6ba46a490aedc408ee88ef056cbaf4e9cb8cb67b2f383e91c7ca80882bb61e0d10bbb790893bb14866fac6a1a77117e35522c116c4504d181bb3960ffb62a8c558368c2dc748894e17ba6bed76b83e31fbbf253fb60dcef8ed433b2372fd052dc63400724ed328
「フラグの暗号文」*「3の暗号文」の復号をします。
╭─────────────────────╮
│ 1. Encrypt flag │
│ 2. Encrypt │
│ 3. Decrypt │
│ 4. Show public key │
│ 5. Exit │
╰─────────────────────╯
> 3
Enter your ciphertext
> 0x4cc5ae6409a83e4a051bcec2425fbcbb503f153420d694b284cceab1e57ba9044e29a0321831dd6905b64b819bdf544e2e8138f2f75b527370cc7a99526259a57a5aeeb89544342c6e24fbfabddabd14c6aebedf1f288879a886a6fcc216589bc7c1f5434a9754d44e5cf46b00941416785b849d471a6759daeeba850ea4b71a467995bd4d9eb9dfaa65efde84a31fe127157d259d7946f106042368caf61c9944ec0a544485c23a2ec1439847332641c4be1a6473a3f0c940f975c09f234c5ca2b05cc237861954e95da6aab56b9b58484a991e9affcd8331a4f4d677ad6d2a0a7e64b959c89ea08908c8241de217dcb7eabcdb98bde16b33352c741b790169001846c13144079d4c5ab5d7c6aef4b82a4a367996cf1517c0cc5ac11483fcc64cdef6435f132c939b4eb0093b1a54305df9d5be34d42bba1ca8a23c88aef08e1ffd3b78ad35c726ce1d559a3c24654b6205b63884406ade9f11841ba674301aa9e79f43ad1007cfdc0f4eda864d1db437ea7a29f3c084d647673b41fbbe2fbf9b5afa06700876b80374f75faefdc496a01032c85acf5d431e36b5e6a14171b86708e389c37b424f07c02d16301f509c5c48e44c14efa8db9c18859148d46df43219fb2bf8c53a4e57a538270559461f34e4dae965b28f07965fa8a24605de7168745a9cc4197bb6bfa1b1dd377481ac0617d1372fae2d1506dc1c209ba6b26c7f9b393b8981795581cf3f8d08c4dfd3eeaeb38b81e15b6974c3261761353f05b0b60d55272feb080f3bf912bd97d8b2df92a36a6b0a698f37e0bcdbe70ad5048bc26ad48f532df830fb08f1dfff2f31a6f52ded87947739459bc3be0c3398e083711a0f9a223bd6dc0ca5abf9a7b6c5c218ed20f70ad2f145d9cd29cbcee63c2b62a117392e6c0d666f589c3e5ab585293a430de3bb4ec6a6ba46a490aedc408ee88ef056cbaf4e9cb8cb67b2f383e91c7ca80882bb61e0d10bbb790893bb14866fac6a1a77117e35522c116c4504d181bb3960ffb62a8c558368c2dc748894e17ba6bed76b83e31fbbf253fb60dcef8ed433b2372fd052dc63400724ed328
plaintext = 0x464c41477b4f555f643065735f6e30745f726570726535336e745f4f73616b615f556e69766572736974795f6275745f4f6b616d6f746f2d5563686979616d6180
このplaintextは「フラグ+3」になっているので、3を引くと正しいフラグが得られました。
plaintext = 0x464c41477b4f555f643065735f6e30745f726570726535336e745f4f73616b615f556e69766572736974795f6275745f4f6b616d6f746f2d5563686979616d6180
print(long_to_bytes(plaintext - 3))
# b'FLAG{OU_d0es_n0t_repre53nt_Osaka_University_but_Okamoto-Uchiyama}'
式で表すとこんなイメージ。
$$ Dec(Enc(flag) \cdot Enc(3)) = flag+3 $$
注意点ですが、この暗号には暗号化を行う際に乱数が用いられています。そのためサーバーに接続しなおすと、フラグの暗号文が異なる値になることがわかると思います。
補足
Okamoto Uchiyama CryptoSystem に次のように記載されています。
Like many public key cryptosystems, this scheme works in the group $(\mathbb {Z} /n\mathbb {Z})^{*}$. This scheme is homomorphic and hence malleable.
準同型暗号って便利そうだなと思いますが、「malleable」という性質も持ちます。
詳しくはこちら。
おまけ
【2019年度未踏／No.15】準同型暗号によるバーチャルセキュアプラットフォームの開発は、準同型暗号の応用例です。面白かったので、興味ある方はぜひ見てみてください。(参考)
おしまい
読んでいただきありがとうございます。
ご指摘がありましたら是非お願いします。