xiyi

本質パートだと思っている場所

• p,q: 518 bit 素数 を自由にとる
• $n := p^2q, g := (n-1)/2$ とする
• 0 ≤ y < 2^256 が隠されている
• s を自由にとる。 $v := s^yg^r \mod p^2q$ が与えられるので、$y$ を復元せよ。ただし $r$ は生成される乱数で、こちらからはわからない

アイデア

• $g = -1/2 \mod p^2, g = -1/2 \mod q$ である
• 問題を言い換えると、
  • $s_p \mod p^2, s_q \mod q$ を好きに決める
  • $v_p := s_p^y (-1/2)^r \mod p^2$
  • $v_q := s_q^y(-1/2)^r \mod q$
  • が与えられる、 y を復元
• $t_p,t_{p^2},t_q$ を $-1/2$ の $\mod p,p^2,q$ での order とする
  • $t_p | (p-1), t_q|(q-1)$
  • $t_{p^2} = t_p$ or $t_p \cdot p$ 普通後者
• $s_p = p+1$ と取ってみる
  • 仮に $t_{p^2}$ が小さいなら、$(-1/2)^r \mod p^2$ を全探索して破綻なく y が取れるかを確認できる
  • $t_{p^2} = t_p$ なら (つまり、 -1/2 を累乗して mod p で 1 になったタイミングで mod p^2 でも 1 になっているなら) 一意には定まるが
• $q$ 側の情報をどう使うんだ?
  • $s_q = 1$ にすれば、 $(-1/2)^r \mod q$ を求められるけど
  • q の情報を使えるんだとしたら、この値から p に関してなにか言えるのか?
  • だとすると、 $t_p, p, t_q$ あたりの gcd がでかい、みたいなことが必要?
• そもそも p = (2 * 3 * 5 * … * prime_i) * k + 1 みたいな形の素数にすれば、離散対数が簡単に解ける by koba
  • 確かに
• p も q もこんな感じのにすればどっちも離散対数が解ける
• ここでいう離散対数が解けるというのは要は
  • $q$ 側では、 $s_q = 1$ とすることで $r \mod t_q$ がわかる
  • $p$ 側では、$s_p = -1/2$ とすることで $y+r \mod t_{p^2}$ がわかる
• ここで $p,q$ を上述の形にとれば $\gcd(t_{p^2},t_q)$ が十分大きくなるので、 $y$ が一意に復元可能