Recovering cryptographic keys from partial information, by example
参考文献
Recovering cryptographic keys from partial information, by example
eが小さく、mの大部分がわかっている時
のようなとき。
とおいて
について
だから、こののsmall rootsを求めれば良い
pの上位半分がわかっているとき
と表して、既知、未知のとき
について
なので、適当なBound をおいて、small root を探す
このsmall rootを探すには
をLLLして出るからとサイズを小さくした方程式をつくって、これの small rootを探せば良い
どうしてmod pの方程式の解がNを使って求められるんですか?
May先生がそういうcoppersmith's methodの拡張をやってくれたから
上記の行列のそれぞれの行が のときに で0になるから(多分)
PRIME_SIZE = 512 KNOWN_SIZE = 270 p = random_prime(1<<PRIME_SIZE) q = random_prime(1<<PRIME_SIZE) n = p * q high_p = p >> (PRIME_SIZE - KNOWN_SIZE) << (PRIME_SIZE - KNOWN_SIZE) PR.<x> = PolynomialRing(Zmod(n)) f = high_p + x set_verbose(2) r = f.small_roots(X=2^(PRIME_SIZE - KNOWN_SIZE), beta=0.25, epsilon=0.005) p_ = int(r[0] + high_p) assert p == p_
pの下位半分がわかっている時
で既知、未知のとき
同様に
として解くだけ
PRIME_SIZE = 512 KNOWN_SIZE = 270 p = random_prime(1<<PRIME_SIZE) q = random_prime(1<<PRIME_SIZE) n = p * q MOD = 1<<KNOWN_SIZE low_p = p % MOD PR.<x> = PolynomialRing(Zmod(n)) f = low_p + x*MOD f = f.monic() set_verbose(2) r = f.small_roots(X=2^(PRIME_SIZE - KNOWN_SIZE), beta=0.25, epsilon=0.005) p_ = int(low_p + r[0]*MOD) assert p == p_
pの上位半分とqの下位半分がわかっている時
pの真ん中半分がわかっている時
で既知、未知の時
適当なBound があって
次のような関数
に対して
だから、多変数多項式 のsmall rootsが求まれば良い
多変数多項式のsmall rootsが求まるような行列をどうやって作るのか……? なんでこうなるんだろう。
[** の上位半分がわかっているとき]
の上位bitがわかっている。すなわち
で既知、未知の時
より
したがって
とすると
とおくと
なので、pの上位bitがわかっているときと同様に解ける
一方[* の下位半分]がわかっていてもを求めるのが難しい