暗号学入門

公開鍵暗号系を構築するための2大数論問題

ー素因数分解問題

・RSA暗号で利用される(1978) ...公開鍵暗号方式の現在の標準

・馬鹿でかい数字を素因数分解しようとしても元の素数のペアを特定するのは難しいよってお話

ー離散対数問題

・DH鍵配送方式で利用される(1976)

・ElGamal暗号で利用される(1985)

・指数部を求めようとしても無理だよってお話

ー対話証明

PとVのデータのやりとり(対話)の後、VはPの主張(命題Xが真であること)が正しいと(非常に高い確率で)確信する(=受理する)

https://gyazo.com/f5fc9e7b7b6f922d29a6f30482a33f20

離散対数問題において、ゼロ知識証明(対話証明の一種)を使用した場合...

VはPがy≡gx (mod p) となるxを知っているに違いないと確信する。しかしVはxに関する情報を得ることができない

ー 有限体

ー線形結合

ーSchwartz-Zippleの補題

ーKEA(Knowledge of Exponent Assumption: 指数知識の仮説)