名前は発明した３人の名前の頭文字に由来する。(R. L. Rivest、A. Shamir、L. Adleman)
●作成の手順①【公開鍵と秘密鍵を生成】(抽象)
pq＝nとする(公開鍵)
（p-１）（q-１）と互いに素な自然数eを任意にとる(公開鍵)
●作成の手順①【公開鍵と秘密鍵を生成】(具体)
p＝７、q＝５
n＝７×５＝35
（p-１）（q-１）＝６×４＝24より、e＝５とする(24と互いに素ならば5以外でもOK)
d＝５とすると、ed÷（p-１）（q-１）＝１余り１
n＝７×５＝35
（p-１）（q-１）＝６×４＝24より、e＝５とする(24と互いに素ならば5以外でもOK)
d＝５とすると、ed÷（p-１）（q-１）＝１余り１
●作成の手順②【メッセージを暗号化】(抽象)
送りたいメッセージを自然数xとする。ただしx＜nとする
xをe乗し、これをnで割った余りをyとする
xをe乗し、これをnで割った余りをyとする
●作成の手順②【メッセージを暗号化】(具体)
x＝12とする。これはx＜nを満たす（n＝35）
12を５乗し、これを35で割ると余りy＝17となる
12を５乗し、これを35で割ると余りy＝17となる
●作成の手順③【メッセージを復号】(抽象)
yをd乗する
これをnで割った余りが平文xとなる
これをnで割った余りが平文xとなる
●作成の手順③【メッセージを復号】(具体)
17を５乗する
これを35で割った余りが平文12となる
これを35で割った余りが平文12となる
RSA暗号の説明
暗号化：暗号文=平文＾E modN
{E,N} のペアが公開鍵に相当します。
{E,N} のペアが公開鍵に相当します。
復号：平文=暗号文＾D modN
{D,N} のペアが秘密鍵に相当します。
{D,N} のペアが秘密鍵に相当します。
N=p⋅q （p,q はそれぞれランダムで十分に大きい素数）
L=lcm(p−1,q−1)｛L は前述の式には登場しない値ですが、残りの値を求めるために利用します。｝
※lcm とは最小公倍数 (Least Common Multiple) 。
※lcm とは最小公倍数 (Least Common Multiple) 。
1<E<L
gcd(E,L)=1
※gcd とは最大公約数 (Greatest Common Divisor)。つまり E,Lは 互いに素 な任意の整数。
gcd(E,L)=1
※gcd とは最大公約数 (Greatest Common Divisor)。つまり E,Lは 互いに素 な任意の整数。
1<D<L
E⋅D=1 modL
つまり Dは Eとの積の余剰が 1 となる任意の整数です。
E⋅D=1 modL
つまり Dは Eとの積の余剰が 1 となる任意の整数です。
参考にさせていただいたサイト
文献
RSA暗号を可能にしたEulerの定理
