これは前述のように、素因数分解の困難性 を利用して一方向の 関数 を得ています。直観的に言うと、7x13 → 91 と計算するのは簡単だ けど、91 がどの２つの素数が掛け合わさっているかを調べるのは簡単ではない （最悪、しらみつぶしに試すしか方法がない？）ということです。
…という説明はかなりおおざっぱです。実際のところ、この方法をきちんと理 解するにはある程度の数学的知識がないと無理なのですが、ここではそこをな んとかして（？）できるだけ簡単に（でもまだ結構複雑かも）説明します。
ちなみに RSA 暗号は Rivest, Shamir, Adleman という３人の研究 者によって考案されたもので RSA とはそれぞれの名前の頭文字を取って付け られたものです。彼らは会社 (RSA Security 社）をつくり、RSA暗号のアルゴ リズムは1983年9月20日にアメリカ合衆国で特許（4,405,829号）が成立しライ センスを独占していましたが、特許期間満了に伴って2000年9月6日からは誰で も自由に使用できるようになりました。
定義から明らかに１は素数ではないです。なぜそうなってるかというと、１を 素数にするとあらゆる整数が割り切れてしまうということになり、意味がなく なるからです。次に、素因数分解についてです。素因数分解とは
24=2*2*2*3のように、ある数を素数のかけ算 の形にすることです。そして （ここでは証明は略しますが）素因数分解は順番をのぞいて１通り です。多くの場合は昇順＝小さい数から先に書く（だんだん大きい数になっ ていく＝昇っていく）ことが多いです。この素因数分解が RSA の基盤になって います。2*2*2*3 を計算するのは簡単ですが、24 が何の積になっているかは一 般には割り算を手当たりしだいしないと分らない、ということで、数が大きく なると大変な処理になるというわけです。
たとえば100までの素数を知りたいとすると2から√100 (=10) まで の素数の倍数を消していくのです。
残った数が素数であることは明らかです（？）…例として97について考えます。ちなみに JavaScript で書いた1000までの素数を求 めるスクリプト例 です。☆ふるい落とされたすべての数について、同じことが言えます。
- もし97 が素数でないと仮定すると、
97＝α*β*...のように素因数分解され、このとき、α、β…のどれかは√100=10までの素数 になるはずです。なぜなら全てが10より大きい素数だったら97は 10*10(*...10) である100より大きくなるからです。- α、β…のどれかは√ 100=10 までの素数になるのでそれをαとすると、 97＝α*β*... ということは97がαの倍数（β*...倍）なので、αの倍数の ときにふるい落とされているはずなので矛盾します。
- よって仮定は偽、つまり97が合成数ではなく素数ということになります。（背理法）
これは、言ってみれば0, 1, 2, 3 ……というふうに、普通の整数は、どこまで も延々と続くのですが、あるところまで行くと 0 に戻る、という（循環した） 世界を考える、ということです。例えば、5 まで行くと次は 0 に戻ると考えま す。5+1は、ふつうの計算では6ですが、この世界では6は0に等しいとします。 つまり、この世界では0,1,2,3,4,5 の６通りしかないことになり、これは６ で 割った余りの世界 と考えることができるわけです。この 「余りの世界」 のことを、「剰余系」 と呼びます。
以下では、通常の計算とこの特殊な世界の計算の両方を使うので、混乱しない ように特殊な世界の等しいは ≡ （合同記号）で表します。すると
0+1=1, 1+1=2, 2+1=3, 3+1=4, 4+1=5, 5+1=6≡0, 6+1=7≡1, 7+1=8≡2, ...37≡1などとなります。すなわち「6を6で割ると余りは0」「37を6で割ると余りは1」 と解釈できます。
何で割ったときの余りかを明示するために、
37≡1 (mod 6)と書いて「6を法 (modulo) にすると37と1は等しい（または37と1は 合同 ）」と言います。このように≡の「等しい」は何を法にするか によって成り立ったり成り立たなかったりするので注意が必要です。とはいえ 前後の流れから分かるときは、法を明示しない場合もあります。
19 + 36 = 55 ≡ 5 (mod 10)これは55を10で割ると余りは5だ、ということです。そして
19≡9 (mod 10) 36≡6 (mod 10) 19 + 36 ≡ 9 + 6 = 15 ≡ 5 (mod 10)というふうに、先に余りを求めて、余りどうしを足しても、結果は同じです。 実際、商 q1, q2 と余り r1, r2 を使って
a = 10q1 + r1 b = 10q2 + r2となっているとき、和
a + b = 10(q1+q2) + (r1+r2)の右辺第一項は10で割り切れるので、a+b を10で割ったときの余りは (r1+r2) にのみ依存します。これは先に余りを求めて 余り同士を足しても同じ、ということを意味しています。法が10の場合は、要 するに１０進数の下１桁だけ計算すればいい、ということで直観的に理解でき ると思いますが、法は10でなくても同じことです。特に乗算の場合には、先に 余りを求められることが役立ちます。
12345678912≡2 (mod 10) 9876543≡3 (mod 10)なので、この場合、12345678912 x 9876543を実際に計算しなくても、この積の 剰余を求めるだけなら 2x3→6 (mod 10) になります。また、
98765434≡34=81≡1 (mod 10)などとできます。9876543の4乗を10で割った余りを計算する時には、素直にこ の数の4乗など計算しなくても、先に10で割って、その余りを4乗するだけで良 いです。
27 = 128 → 7で割ると商18、余り2 37 = 2187 → 7で割ると商312、余り3 47 = 16384 → 7で割ると商2340、余り4 57 = 78125 → 7で割ると商11160、余り5 ……というふうになり、余りは7乗されたもとの数に戻ります。式で書けば、
np ≡ n (mod p)となります。例えば、
107 = 10000000の場合、7で割ると商1428571、余り3ですが、3は7を法として10と合同ですから、やっぱり
107 ≡ 10 (mod 7)が成り立ってます。「7で割った余りで考える世界」では、3も10も73も同じグ ループとして同一視するということです。
フェルマーの小定理は「pを法とする世界で考えると、どんな数もp乗すれ ば自分自身に戻る」ととらえることができます。つまり、上で見た通り、 例えば7を法とした世界では、3 の7乗は3自身と合同、4の7乗は4自身と合同、 5の7乗は5自身と合同…となります。再掲しますので再確認してください。
27 = 128 → 7で割ると商18、余り2 37 = 2187 → 7で割ると商312、余り3 47 = 16384 → 7で割ると商2340、余り4 57 = 78125 → 7で割ると商11160、余り5 ……上の各行の左端には2とか3とか4とか5があって、右端には、ふたたびその左端 の数が現れてます。このことを公開鍵暗号系のイメージと重ねると、暗号化と 復号化の合成写像がちょうど上の計算になるようにうまく定義すると、受信者 は暗号化された文章をもとの文章に復元できる、ということがなんとなくイメー ジ出来ると思います。この計算は「もとに戻ることが保証されている」 ところが重要です。すなわち、いくら解読が難しい暗号文を作っても元に 戻せなければ意味が無いというわけです。
素数ではない場合には、この式はなりたちません。例えば、
38 = 6561 → 8で割ると商820余り1となって、余りは3に戻りません。つまり素数じゃない8ではうまくいかないで す。しかし、
35 = 243 → 5で割ると余り3 37 = 2187 → 7で割ると余り3のように、指数が5や7といった素数のときは、ちゃんと余りがもとの数と合同 になります。
ap-1≡ 1(mod p)となります。これは、元の定理の両辺をaでわれば簡単に導かれます。さらに 系として
ax≡ a(mod p)」となります。この系がRSAでは重要な役割りをはたします。
というのは、非常におおまかに説明すると x-1 は p-1 で割り切れるので、あ る整数 q によって x-1=q(p-1) と書け、a'=a (mod p) とするとax ≡ (a')x ≡(a')q(p-1)+1 ≡ (a')q(p-1)*(a') ≡ ((a')p-1)q*(a') ≡ 1q*(a') ≡ a' ≡a(mod p)であるからです。
gcdとは与えられた２つの数の最大公約数です。つまり、それが １ということは、互いに素（＝素因数分解した時に、共通する素因数が無い） ということです。この公開指数 e と係数 n が公開鍵 (e,n) となります。
C≡Me (mod n) M≡Cd (mod n)これらの関係式が必ず成り立つという（数学的）特性が RSA 暗号の原理 です。これは上のフェルマーの小定理を使うことにより証明できますが、 詳細は略します。
…だけではなんなので、大まかな説明は以下の通りです。ここでいくら暗号文 C, 係数 n および公開指数 e の値を知っていたとし ても、秘密指数 d の値を知らなければ暗号文 C から平文 M を得ることは （計算量的に）ほぼ不可能 です。これがRSA暗号の安全性の保証と なってるわけです。
- e*d-1は (p-1)*(q-1) で割り切れるので、e*d-1 は p-1 で割り切れる ゆえに e*d≡1 (mod (p-1))
- これをフェルマーの小定理の系に適用して、 Cd≡(Me)d≡Me*d≡M (mod p)
- よって Cd - M ≡0(mod p)
- 同様の計算を q に対しても行い Cd - M ≡0 (mod q)
- ここで p,q は素数なので互いに素（割れない）なので、上の式の左辺は p*q=n で割り切れる。つまり Cd - M ≡ 0 (mod n)
- よって Cd ≡ M (mod n)
ちなみに、一度に暗号化できるデータは n 以下の数値 であることも 留意してください。例えば n が 1024bit の数値であれば、長い平文であった 場合はその 文字コード＝数値 を（安全を見越して） 1023bit 以下 毎に分けてから暗号化しないといけないことになります。
ただし分かりやすくするために非常に小さい＝安全でない鍵を使っている、と いうことは把握しておいてください。現実社会では最近では計算機能力の向上 にあわせて2048 (or 4096)bit長の数値を使っています。
文書を数値化するというのは特別な仮定ではなく、一般的なことです。たとえ ば "ABC" という文字列は ASCII では16進数で '414243' となりますが、これ は 65*256*256+66*256+67=4276803という整数として扱うことが出来るわけです。そのためにAさんは秘密鍵 (d,n) を、Bさんはそれに対応する公開鍵 (e,n) をそれぞれ持っていなければなりません。まず A さんはそれらを作成 します。
n = 7*11 = 77 φ(n) = 6 * 10 = 60となります。
この e も、下の d にしても、元の素数から一意に決まるわ けではなく、条件を満たせば任意のものが選べます。
d*e=37*13=481≡1(mod 60)となっています。
Me = 313 = 1594323 ≡ 38 (mod 77) ⇒ C=38Bさんはこの暗号文C=38をメールでAさんに送ります。
Bさんから送られた暗号文を受け取ったＡさんは、早速上述した復号化の式を使って
Cd = 3837 = 28313468473157736370011296127792731029354930758695159595008 ≡ 3 (mod 77) ⇒ M=3以上のような暗号処理によりAさんはBさん以外の誰にも重要文書の元の内容を 知られることなく無事にその内容M(=3)を得られます。
ちなみに署名についても上とほぼ同様で、MD5 かなにかでダイジェスト（ハッ
シュ）をつくって、それを自分の秘密鍵で暗号化すれば、それを元に戻せるの
は自分の公開鍵だけですから認証できるわけです。
もし素因数分解を簡単に行うことができれば、RSAを破ることは可能です。公 開鍵 (e, n) を知っていて、もし n を素因数分解して p,q を知ることができ れば秘密指数dはそれらから簡単に計算できます。とはいえ、例えば n が 2048bit だと10進数で六百桁くらいの数値なので、素因数分解するのに何十年 もかかる＝現実的には解けない、という期待なわけです。
とはいえ量子コンピュータが実現すれば比較的簡単にとけるとされていますし、 そもそも n を素因数分解することだけがRSAを破る唯一の方法かどうかは分かっ ていない（証明されていない）のが現状です。
何故このような問題が起こるのかと言えば、RSA暗号の使い方が誤っているか らなのです。つまり平文の「場合の数」（種類）が少ければ、その 数だけを試すことで解けるからです。
なので、この場合は内容である名前の前（か後ろ）に大きな乱数を連結 （「1357前田」のような形式）した上で暗号化すれば解決できます。
このような追加するデータのことをソルト と呼ぶことがあります。例えば乱数の大きさと して 128 ビットを取れば、投票された暗号データを盗聴した者は５通りではな く5x2128 通り の暗号化及び比較をしなくてはならなく なりますが、それは計算量的に不可能、というわけです。