一方向性関数

情報処理振興事業協会「暗号強度評価に関する調査研究調査報告書」より抜粋

具体的な一方向性関数としては次のようなものが挙げられる。gを有限体GF(p)における原始根としたとき、y=gx mod p を計算する事は容易であるが、逆にg,p,yが与えられたときにxを計算することは困難であると考えられている（離散対数問題）。よってこの計算は一方向性をもち、関数f(x)= gx mod pは一方向性関数と言える。また、桁の大きい素数pとqが与えられたとき、両者の積n=pqを計算することは容易であるが、nが与えられたときにpとqに素因数分解することも困難であると考えられている（素因数分解問題）。よって関数f(p,q)=pqも一方向性関数であると言える。実際に、ここで挙げた二つの一方向性関数を用いた公開鍵暗号が存在する。離散対数問題の困難性に基づくものとして代表的なものには、ElGamal暗号、素因数分解問題の困難性に基づくものとしては、RSA暗号などがある。