<背景> 暗号文、平文ともに、正の整数とする。

以下の式によって、暗号化、復号化を行うこととする。

暗号文 = 平文のe乗 mod p*q
平文 = 暗号文のd乗 mod p*q

ここで、d = (n*(p-1)(q-1)+1)/e (今回は簡略化のためn=1）とする。　

受信者Ａさんが、送信者Ｂさんから、暗号を受け取りたい。

受信者　Ａさん：　p, q, eを決め、p*qの積とeのセットを公開鍵として、Ｂさんに送る（公開する）。
送信者　Ｂさん：　上の式に従って、平文を暗号化し、暗号文をＡさんに送る
受信者　Ａさん：　上の式に従って、秘密鍵dを計算しておき、暗号文を、平文に復号する。

デジタル署名　（秘密鍵で暗号化すれば、公開鍵で復号できることを利用）

受信者Ｂさんは、送信者が Aさんであることを、確認したい。

送信者　Ａさん： p, q, 公開鍵eを決め、p*qとeをBさんに送る
送信者　Ａさん：平文１と、秘密鍵dで平文を暗号化した暗号文の2つを送る

受信者　Ｂさん：暗号文を公開鍵で復号し、平文２を得る
送信者　Ｂさん：Ａさんから届いた平文１と、復号した平文２が一致するなら、Ａさんである。（平文は、Ａさんしか知らないはずである）

というのがエッセンス。実際は、Ａさんが送る平文１に、さらに安全性を高める工夫がある。
この方法には、
（１）送信者がＡさんであること、（２）送られてきた平文に改ざんがないことを確認できる

<問題> 上の暗号化のプログラムと、復号のプログラムを作成せよ。

<実行例>
素数p = 3
素数q = 11
公開鍵e = 7
平文 = 9　（←　ここまで入力。Bさんは、33と7しか伝えられない.33は素因数分解できるが、現実にはもっと大きな２つの素数を使い、大きな積を公開する）
暗号文 = 15　（Ｂさんは、暗号文15を送信する）

素数p = 3　
素数q = 11
公開鍵 = 7　（←　ここまで入力すると、下を表示。Ａさんは、ここまで準備できている）
秘密鍵 = 3　
暗号文 = 15　（Bさんから届いた暗号文15を、準備に従って復号すると、下）
平文 = 9　（Ａさんは9と復号、解読）

矢沢久雄 : "素因数分解とRSA暗号" 日経ソフトウェア　2010年8月号付録 (プログラムを改変）

解答例
/* 暗号化 */
#include <stdio.h>

int main (void) {
   unsigned int p, q, pubkey, plaintext, ciphertext, i;

   printf("素数p = ");
   scanf("%u", &p);

   printf("素数q = ");
   scanf("%u", &q);

   printf("公開鍵e = "); /* public key */
   scanf("%u", &pubkey);

   printf("平文 = ");
   scanf("%u", &plaintext);

   ciphertext = 1;

   for (i = 1; i <= pubkey; i++)
     ciphertext *= plaintext;  /* plaintextの数をpubkey乗する */

   ciphertext %= p*q; /* 素数pとqの積で割った余りが、暗号文 */

   printf("暗号文 =  %u\n", ciphertext);

   return 0;
}

/* ここからは、復号のプログラム。別のプログラムです。
 それぞれ、別のファイルに作成、コンパイルして実行のこと */
#include <stdio.h>

int main (int argc, char *argv[]) {
   unsigned int p, q, pubkey, prikey, ciphertext, plaintext,i;
   unsigned int n;
   n = 1;

   printf("素数p = ");
   scanf("%u", &p);

   printf("素数q = ");
   scanf("%u", &q);

   printf("公開鍵 = ");
   scanf("%u", &pubkey);

   prikey = (n*(p -1)*(q-1) + 1)/pubkey;
   printf("秘密鍵 = %u\n", prikey);

   printf("暗号文 = ");
   scanf("%u", &ciphertext);

   plaintext = 1;
   for (i = 1; i <= prikey; i++)
      plaintext *= ciphertext;

   plaintext %= p*q;

   printf("平文 = %u\n", plaintext);

   return 0;
}

簡略RSA暗号