[DASCTF 2020四月春季試合]not_RSA問題解
テーマ分析
テーマの内容
*この問題はPaillier暗号化スキームですが、問題を解くときは知りませんでした.
c,n＝p⋅q,g＝n＋1が知られている.0暗号化プロセスは:暗号化プロセスは:暗号化プロセスは:c≡gm(m o d n 2)r n(m o d n 2)(m o d n 2)(m o d d n 2)≡gmr n(m o d d n 2)c≡g^m(modn^2)cdor^n(modn^2)(modn^2)\\\\equivg^m r^n(modn^2)c≡gmgm(mod n 2)(mod n 2)(mod n 2)≡gmm(mod n 2)≡gmm m m m(mod n 2)(mod n 2)(mod n 2)≡gmm m m m m m m m m m m m n 2)rn(mod n 2)
問題を解く構想.
未知量rとmが2つあり,まずrを求めることを考慮した.0g=n+1,c≡g m⋅r n(m o d n 2)注意g=n+1\,\c≡g^mcdot r^n(modn^2)注意g=n+1,c≡gm⋅rn(mod n 2)
一方、g mの二項式展開により、g m≡1(m o d n)が分かりやすく、g^mの二項式展開により、g^mequiv 1(modn)がわかりやすく、gmの二項式展開により、gm≡1(mod n)がわかりやすい.
従って,r n≡c(m o d n)である.この方程式を解くにはnの分解が要求される.したがって、r^nequiv c(modn)となる.この方程式を解くにはnの分解が要求される.従ってrn≡c(mod n)である.この方程式を解くにはnの分解が要求される.
y a f uでp,qを求める.計算＃ケイサン＃φ (n)=(p−1)(q−1)yafuでp,qを求める.計算varphi(n)=(p-1)(q-1)yafuでp,qを求める.計算＃ケイサン＃φ(n)=(p−1)(q−1) .
( n , φ (n))=1であるためd=n−1(m o dφ (n)),r≡(r n)d(m o d n)(n,varphi(n))=1となるのでd=n^{-1}(mod\varphi(n)),requiv(r^n)^d(modn)(n,φ(n))=1であるためd=n−1(mod)となるφ(n)),r≡(rn)d(mod n)を得る
次に、c≡g m
m n + 1 ≡ c ⋅ r − n ( m o d n 2 ) ⟺ n m ≡ c ⋅ r − n − 1 ( m o d n 2 ) mn+1\equiv c\cdot r^{-n}\(mod\n^2)\iff nm\equiv c\cdot r^{-n}-1(mod\n^2) mn+1≡c⋅r−n (mod n2)⟺nm≡c⋅r−n−1(mod n2)
a=c⋅r−n−1と記す.n∣aであるため、上式左右と型をnで割って、a=ccdot r^{-n}-1と記すことができる.n|a,\だから上式の左右と型をnで割って、a=c⋅r−n−1と記すことができる.n∣a、だから上式の左右に対して型と同じでnを割ることができて、m≡a n(m o d n)\mequivdfrac{a}{n}(modn)m≡na(mod n)を得て次は解釈しないで連招して次は解釈しない連招して次は解釈しない連招して次は解釈しない連招して次は解釈しない連招します
exploit.py (solve.py)
TODO:Pailier案まとめ
テーマの内容
*この問題はPaillier暗号化スキームですが、問題を解くときは知りませんでした.
c,n＝p⋅q,g＝n＋1が知られている.0
問題を解く構想.
未知量rとmが2つあり,まずrを求めることを考慮した.0
一方、g mの二項式展開により、g m≡1(m o d n)が分かりやすく、g^mの二項式展開により、g^mequiv 1(modn)がわかりやすく、gmの二項式展開により、gm≡1(mod n)がわかりやすい.
従って,r n≡c(m o d n)である.この方程式を解くにはnの分解が要求される.したがって、r^nequiv c(modn)となる.この方程式を解くにはnの分解が要求される.従ってrn≡c(mod n)である.この方程式を解くにはnの分解が要求される.
y a f uでp,qを求める.計算＃ケイサン＃φ (n)=(p−1)(q−1)yafuでp,qを求める.計算varphi(n)=(p-1)(q-1)yafuでp,qを求める.計算＃ケイサン＃φ(n)=(p−1)(q−1) .
( n , φ (n))=1であるためd=n−1(m o dφ (n)),r≡(r n)d(m o d n)(n,varphi(n))=1となるのでd=n^{-1}(mod\varphi(n)),requiv(r^n)^d(modn)(n,φ(n))=1であるためd=n−1(mod)となるφ(n)),r≡(rn)d(mod n)を得る
次に、c≡g m
m n + 1 ≡ c ⋅ r − n ( m o d n 2 ) ⟺ n m ≡ c ⋅ r − n − 1 ( m o d n 2 ) mn+1\equiv c\cdot r^{-n}\(mod\n^2)\iff nm\equiv c\cdot r^{-n}-1(mod\n^2) mn+1≡c⋅r−n (mod n2)⟺nm≡c⋅r−n−1(mod n2)
a=c⋅r−n−1と記す.n∣aであるため、上式左右と型をnで割って、a=ccdot r^{-n}-1と記すことができる.n|a,\だから上式の左右と型をnで割って、a=c⋅r−n−1と記すことができる.n∣a、だから上式の左右に対して型と同じでnを割ることができて、m≡a n(m o d n)\mequivdfrac{a}{n}(modn)m≡na(mod n)を得て次は解釈しないで連招して次は解釈しない連招して次は解釈しない連招して次は解釈しない連招して次は解釈しない連招します
exploit.py (solve.py)
#coding=utf-8
from gmpy2 import *
from Crypto.Util.number import long_to_bytes
p = 80006336965345725157774618059504992841841040207998249416678435780577798937819
q = 80006336965345725157774618059504992841841040207998249416678435780577798937447
n = 6401013954612445818165507289870580041358569258817613282142852881965884799988941535910939664068503367303343695466899335792545332690862283029809823423608093
c = 29088911054711509252215615231015162998042579425917914434962376243477176757448053722602422672251758332052330100944900171067962180230120924963561223495629695702541446456981441239486190458125750543542379899722558637306740763104274377031599875275807723323394379557227060332005571272240560453811389162371812183549
g = n + 1
# c = g^m * r^n (mod n^2) =>
# c mod n = g^m * r^n (mod n)
# And g (mod n) = 1, so g^m = 1 (mod n)
# We got r^n = c (mod n) , and find that (φ(n),n) = 1
φ = (p-1) * (q-1)
# Just solve r like RSA decryption
r = pow(c%n, invert(n, φ), n)
# convert equation to g^m = c*r^(-n) (mod n^2)
# g^m = (n+1)^m = mn + 1 (mod n^2)
# set a = c*r^(-n) - 1,
a = c * pow(invert(r,n*n), n, n*n) % (n*n) - 1
# We have mn = a (mod n^2)
# n|a , n|mn , n|n^2 , So m = a/n (mod n) => m = a/n
m = a//n
flag = long_to_bytes(m)
if __name__ == '__main__':
# print(r)
# print(a)
# print((a-1) % n)
print(flag)
TODO:Pailier案まとめ