現暗号と脆弱性攻撃

現暗号の具体的数値

  • 256ビットの推奨ECC: secp256r1
  • y2 = x3 + ax + b (mod p), 位数:r
  • p=115792089210356248762697446949407573530086143415290314195533631308867097853951
  • r=115792089210356248762697446949407573529996955224135760342422259061068512044369
  • a=115792089210356248762697446949407573530086143415290314195533631308867097853948
  • b=41058363725152142129326129780047268409114441015993725554835256314039467401291
  • Curve(point): Q=(Qx,Qy)
  • Qx=16541727030050892680385349564201081932869449059327187742219090186981013979132
  • Qy=25818268083887228378207107542437174286775255751119128378977759983362344375837

脆弱性攻撃(Invalid Curve Attack)

  • 256ビットの推奨ECC: secp256r1
  • Invalid Curve : Q=(Qx,Qy)を脆弱性攻撃で置き換え
  • Qx=57896044605178124381348723474703786765043071707645157097766815654433548926972
  • Qy=57684798960610185562186990909005320688004873483451899562987949717691690412694
  • 値が変わらない係数: p, a
  • 値が変わる係数 : b, r
  • b=10106
  • r=115792089210356248762697446949407573529658708695050940591319239710041960297572

Invalid Curve Attack(ICA)で高速解読

  • secp256r1の本来の位数rは素数
  • Invalid Curve Attackの位数rは変更され因数分解される
  • r=115792089210356248762697446949407573529658708695050940591319239710041960297572
  • r=4131922108816065318184839304391204672993390200611861937431296502157*42370421023549
  • 素数位数rのECCを解く問題から合成数の各因数のECCを全て説く問題に変更
  • 例: 256ビット問題の解読 –> 2,11,22,43,45,45,46,46ビット問題の解読
  • ρ法で現暗号(secp256r1)が1～2分で解読可能(4Ghzパソコン)

ICAと学習λ法なら瞬時に解読

  • 学習λ法は学習時間に比例して高速化できる。
  • 学習λ法で1日学習するとρ法に比較し約千倍高速にできる。
  • ECC-256は10日間学習させると、約1万倍高速化できる。
  • 各因数への変換の固定部分があり、0.01秒解読が高速化の限界。
  • 立山室堂 (Toyama, japan: 2010/7/20: with family)