• [Neuenschwander 04, 2.4]より。

定理(RSA-HC1)の証明のアイデア


  • うまく a∈Zq* をつくって、有理数[ax]n/nを十分な精度で求めれば、x がわかる。
    • 1/(2n) を超える精度ならばOK.
  • 自明な精度1からはじめて、精度を再帰的に倍加していく。
    • 1/2倍写像をうまく用いる。

定理(RSA-HC1)の証明


整数aについて、[a] := a mod n とかく。
アルゴリズムA2: n, e, y(= xe mod n)を入力として、
  • u0 = 0, a0 = 1
  • t ∈ [1..(l+1)]: (※ l := nのビット長)
    • at = 2-1 at-1 mod n
    • ut = (1/2)・(ut-1 + A1(n, e, [at-1e y]) (∈ Q)
    • ※ ut = (1/2)・(ut-1 + Lsb([at-1 x])
  • return x = al+1-1 floor(ul+1 n + 1/2) mod n.

[アルゴリズムA2の解析]:
t ∈ [1..(l+1)]について、
  • [at x] = [2-1 at-1 x]
    • = (1/2) [at-1 x] (when [at-1 x]: even)
    • = (1/2) ([at-1 x] + n) (when [at-1 x]: odd)
  • = (1/2) ([at-1 x] + Lsb([at-1 x]) n)
よって、
  • | [at x] - ut n | = | (1/2) ([at-1 x] + Lsb([at-1 x]) n) - ut n |
  • = (1/2) | [at-1 x] - ut-1 n |.
| [a0 x] - u0 n | = [x] < n に注意して
  • | [al+1 x] - ul+1 n | < n / (2l+1) < 1/2
よって、
  • [al+1 x] = floor(ul+1 n + 1/2)
ゆえに
  • x = al+1-1 floor(ul+1 n + 1/2) mod n.

Q.E.D.














最終更新:2009年09月02日 01:04