琉球大学工学部情報工学科　吉田たけお

九州工業大学情報工学部電子情報工学科　尾知　博

1．はじめに

  当初は琉球大学工学部の授業の一環として実施していたLSIデザインコンテスト・イン沖縄は、2008年で早いもので第11回を迎えます。その間に、国内の大学・高専からの参加が大幅に増えたばかりでなく、アジアを中心に韓国、インドネシア、ベトナムなどの海外の大学からの参加も順調に増え、今や100件以上もの応募がある大規模な設計コンテストと成長しました。このように、国際的に成長したコンテストを祝して、2008年から優秀な設計チームに、電子情報通信学会（スマートインフォメディアシステム研究会）のアワードの贈呈を検討しています。こうした賞を目指し、学生の皆さんのこれまで以上にユニークな設計を期待しています。

  今回は、第2回コンテストの設計課題として扱ったRSA暗号の暗号化器と復号器の設計をレベル1，2に分けて、第11回の設計課題とします。

2．暗号に関する基礎知識

  RSA暗号について説明する前に、まず、暗号に関する基本的な用語について説明しておきます。
  改めて説明する必要はないかも知れませんが、暗号とは、発信者(sender)が、特定の受信者(receiver)以外には知られたくない情報やデータを、その特定の受信者以外には解らないように秘匿あるいは偽装する手法のことをいいます。
  発信者が特定の受信者に伝えたい情報やデータのことを平文(plaintext)といいます。平文は、誰にでもその意味や内容を把握できる表現になっています。発信者は、この平文を、電話回線、郵便、コンピュータネットワークなどの通信路(communication channel)を介して、受信者に伝送します。しかし、これらの通信路は、第三者に盗聴(tapping)される危険性があります。このとき、情報を不正に入手しようとする第三者のことを盗聴者(wiretapper)といいます。何の対策も施していない場合、盗聴者に、平文をそのまま入手され、さらに、発信者が受信者に伝えたい情報を把握されてしまいます。この様子を図1に示します。
  暗号は、このような情報のやり取りにおいて、盗聴者にそのやりとりの内容が解らないようにするために用いられます。暗号を用いた通信では、平文の意味や内容を盗聴者が把握できない（把握しにくい）ように、平文を変換してから、受信者に送ります。この平文を変換したものを暗号文(ciphertext)といいます。
  ここで、平文を暗号文に変換することを暗号化(encryption)といい、暗号化を行うディジタル回路を暗号化器(encipher)といいます。また受信者が、暗号文を元の平文に戻すことを復号化(decryption)あるいは単に復号といい、復号を行うディジタル回路を復号器(decipher)といいます。なお、盗聴者が不正に入手した暗号文を元の平文に戻すことは解読といいます。 さて暗号文は、受信者には簡単に復号できて、盗聴者には簡単に解読できないようになっている必要があります。そこで発信者は、パスワードを知っている者だけが簡単に復号できるように、暗号文を作ります。このパスワードのことを、暗号の世界では、鍵(key)といいます。発信者は、事前に、受信者だけに鍵を渡しておき、その後、暗号文を送ります。受信者は、受け取った暗号文を、発信者に渡された鍵を使って復号し、元の平文を得ます。一方、盗聴者は、不正に暗号文を入手できますが、鍵が無いので、簡単には解読できません。この様子を図2に示します。

  さて、暗号には、様々の種類のものが存在しますが、それらは秘密鍵暗号と公開鍵暗号に大別できます。以下では、この秘密鍵暗号と公開鍵暗号について簡単に説明します。なお今回の設計課題であるRSA暗号は、公開鍵暗号の一種です。
  既に説明したように、暗号における鍵は、暗号化と復号の両方の処理において用いられますが、暗号化の際に用いられる鍵を暗号化鍵(encryption key)、復号の際に用いられる鍵を復号鍵(decryption key)といいます。ここで、秘密鍵暗号とは暗号化鍵と復号鍵が同じであるような暗号のことを、公開鍵暗号とは暗号化鍵と復号鍵が異なるような暗号のことを、それぞれいいます。
  秘密鍵暗号では、暗号化鍵と復号鍵が同じなので、両者を区別せずに、単に鍵と呼びます。また通常、この鍵は、発信者が作成（生成）し、安全な方法を使って受信者に渡します。秘密鍵暗号を使った通信において、安全性を確保するためには、この「安全な方法で鍵を渡す」こと、すなわち、鍵の情報を第三者に漏らさないこと、が重要になります。このように、鍵を秘密にしておく必要があるので、秘密鍵暗号と呼ばれています。
  一方、公開鍵暗号では、暗号化鍵と復号鍵が異なります。このことを、ドアの鍵に例えると、施錠用の鍵と開錠用の鍵が異なることを意味します。自宅のドアがこのような構造になっていると、不便で仕方ありません。しかし暗号においては、この仕組みは絶大な威力を発揮します。公開鍵暗号の暗号化鍵と復号鍵は、受信者が作成します。そして、暗号化鍵を世間に公開し、復号鍵は秘密に保持しておきます。このため、暗号化鍵のことを公開鍵(public key)、復号鍵のことを秘密鍵(private key)とも呼びます。なお、暗号化鍵を世間に公開するということは、盗聴者にも公開するという意味です。

  ここで、公開鍵暗号を使った通信の概要を、図3を用いて説明します。いま、AさんとBさんの間で、公開鍵暗号を使った通信を行うものとします。Aさんは、独自に、暗号化鍵（公開鍵）EAと復号鍵（秘密鍵）DAを作り、このうち、公開鍵EAを公開します。同様にBさんも、独自に、暗号化鍵（公開鍵）EBと復号鍵（秘密鍵）DBを作り、このうち、公開鍵EBを公開します。まずAさんが、Bさん宛ての平文PBを送る場合、Bさんによって公開されている公開鍵EBを入手します。Aさんは、この公開鍵EBを使って平文PBを暗号化し、暗号文CBを作り、これをBさんに送ります。Bさんは、秘密鍵DBを使って暗号文CBを復号し、Aさんからの平文PBを入手します。このとき、盗聴者が入手可能な情報は、Bさんによって公開されている公開鍵EBと、通信路を盗聴して得られる暗号文CBです。Bさんが、秘密鍵DBを秘密にしておけば、暗号文CBを復号できるのはBさんだけなので、盗聴者に、平文PBの内容が漏れることはありません。なお、暗号文CBを作ったAさんも、秘密鍵DBを知らないので、暗号文CBを元の平文PBに復号することはできません。もちろん、平文PBを作ったのはAさんなので、復号する必要はないのですが、この点が、公開鍵暗号の特徴でもあります。次に、Bさんが、Aさん宛ての平文PAを送る場合も同様で、まず、Aさんによって公開されている公開鍵EAを入手します。Bさんは、この公開鍵EAを使って平文PAを暗号化し、暗号文CAを作り、これをAさんに送ります。この場合も、Aさんが、秘密鍵DAを秘密にしておけば、盗聴者が入手可能な情報から、平文PAの内容が漏れることはありません。このように、暗号化鍵を世間に公開するので、公開鍵暗号と呼ばれています。
  図3の例では、二人の間の通信を例にしましたが、Aさん、Bさんが公開している暗号化鍵を用いれば、誰でも、Aさ、Bさん宛ての暗号文を作れます。公開鍵暗号は、秘密鍵暗号で必要な「安全な方法で鍵を渡す」ことが不要となっていますが、このことを可能にしているのは、暗号化鍵と復号鍵を区別している点にあります。
  公開鍵暗号は、画期的な暗号として様々な分野で使われていますが、暗号化および復号に要する処理時間が、秘密鍵暗号と比較して、非常に長いという短所もあります。そのため実際には、両者を組み合わせて使用します。すなわち、通常の暗号通信には、高速処理が可能な秘密鍵暗号を用いますが、その秘密鍵暗号の鍵を、公開鍵暗号を使ってやり取りします。このようにすれば、両者の短所を補って、安全な暗号通信が行えます。