クエリ: 発明者したロナルド・リベスト、アディ・シャミア、レオナルド・エーデルマンの頭文字からつけられた、現在インターネットで広く用いられる暗号アルゴリズムは何?
文章: RSA暗号 RSA暗号方式は、1977年に発明され、発明者であるロナルド・リベスト、アディ・シャミア、レオナルド・エーデルマンの原語表記の頭文字をつなげてこのように呼ばれる。前年(1976年)にディフィーとヘルマンによって発表されたばかりの公開鍵暗号という新しい概念に対し、秘匿や認証を実現できる具体的なアルゴリズムを与えた。発明者3氏は、この功績によって2002年のチューリング賞を受賞した。この暗号はフェルマーの小定理に基づいている。RSA暗号は次のような方式である。鍵のペア(公開鍵と秘密鍵)を作成して公開鍵を公開する。まず、適当な φ {\displaystyle \phi } と互いに素な正整数 e を選択する。
文章: Data Encryption Standard しかし、同時に次のようなことも判明している。 DES設計チームのウォルト・タックマンは「我々はIBM内でIBMの人員だけでDESアルゴリズム全体を開発した。NSAに命じられて変更した部分は1つもない」と述べた。一方、機密解除されたNSAの暗号史に関する本には次のように書かれている。 Sボックスに関する嫌疑の一部は1990年に鎮められることになった。同年、エリ・ビハムとアディ・シャミア(RSAのS)が差分解読法を独自に発見して公表した。差分解読法はブロック暗号を破る汎用技法である。DESのSボックスは無作為に選ばれた場合よりもこの攻撃法にずっと抵抗力があり、IBMが1970年代にこの攻撃法を知っていたことを強く示唆していた。1994年、ドン・コッパースミスがSボックスの元々の設計基準について一部を公表したことで、それが裏付けられた。スティーブン・レビーによれば、IBMでは1974年に差分解読法を発見していたが、NSAがそれを秘密にするよう要請していたという。コッパースミスはIBMの方針について「(差分解読法)は非常に強力なツールであり、様々な方式に応用でき、これを公にすると国家の安全に悪い影響を及ぼすことが懸念された」と述べている。レビーはタックマンの言葉として「彼らは我々のあらゆる文書に極秘というスタンプを押させようとした...それらは合衆国政府の機密と見なされたので、我々は実際にそれらに番号を振り、金庫に入れた。彼らがそうしろと言ったから、そうしたまでだ」と書いている。 文章: Secure Hash Algorithm SHA-0およびSHA-1が最も古く、(さらにそれ以前のMD5を置き換えて)以前はTLS、SSL、PGP、SSH、S/MIME、IPSecなど、さまざまなアプリケーションソフトウェアやプロトコルに採用されていたが、2004年のCRYPTO2004におけるXiaoyun Wang(王小雲)らの発表以降、広く知られるようになった研究の進展により、2017年2月には実際に衝突攻撃の成功が示されている。よって、2017年初頭の段階でこれらを情報セキュリティの目的で使用しているのは無謀である。SHA-2までは国家安全保障局 (NSA) によって開発された。1993年に発表された最初のものは、公式には単にSHAと呼ばれていた。しかし現在は、その後のものと区別するためにもっぱらSHA-0と呼ばれている。1995年に弱点を修正したSHA-1が発表された。 文章: 暗号理論 英語では、暗号を cryptography といい、暗号学を cryptology という。また、日本ではもっぱら総称される暗号には、「コード」と「サイファ (en:cipher)」という分類がある。暗号理論は、暗号学の一分野である。暗号の理論の主な分野には、以下のようなものがある。暗号理論は暗号学の一分野であり、暗号学の全ては理論ではカバーしきれない。古典的な暗号に比べれば現代の暗号(現代暗号)は理詰めで構成されている。 それでも、暗号学としては、その運用や関与する人間の不注意といったヒューマンファクタなども考慮しなければならない。(「暗号の連鎖(chain)の強さは、最も強い環(link)の強さしかない」ということは変わっていない。)コンピュータセキュリティやネットワークセキュリティ、より総合的には情報セキュリティと暗号や暗号理論とは密接な関わりがある。 文章: 秘話 デジタル方式の第2世代携帯電話の初期のものとしてGSMがある。1987年に規格の基本部分が決められ、音声の暗号化のためA5/1と呼ばれる方式が採用され主にヨーロッパで使用された。その後A5/1の暗号強度を落とした派生方式のA5/2も採用され、その他の地域で使用されている。これらの方式には脆弱性があることがわかっており、鍵ストリーム生成のコアとなるアルゴリズムとしてKASUMIを使用するA5/3と呼ばれる方式も2002年に標準として採用された。 A5/1はストリーム暗号の一種で、鍵ストリームの生成には3つの線形帰還シフトレジスタ (LFSR) を組み合わせて使用する。各シフトレジスタにはクロックビットがあり、これらの多数決の結果と自身のクロックビットが等しい場合のみシフトを行わせる。クロックを不規則にすることで単純なLSFRより解読が難しくなる。暗号鍵の長さは64ビットで、同じ鍵ストリームの生成を防ぐためシフトレジスタの初期値には暗号鍵と22ビットのフレーム番号とを用いる。 A5/1のアルゴリズムは非公開だったが、GSMは比較的早い時期から広く使われていたためアルゴリズムの解析やA5/1の解読方法の研究も早い時期から行われた。GSM携帯端末のリバースエンジニアリングにより1999年にアルゴリズムが解析され、一般に公開されていたテストデータにより結果が検証された。2000年には通常のPCを使いリアルタイムで暗号鍵を見つけ出すことができる方法が論文として発表された。またGSMのプロトコル上の脆弱性を利用し最も暗号強度の弱いA5/2を使わせることで秘密鍵を見つけ出す方法も考案されている。 文章: マックエリス暗号 マックエリス暗号は,鍵を生成する確率的アルゴリズム,暗号化をする確率的アルゴリズム,復号アルゴリズムの,3つのアルゴリズムから成る.マックエリス暗号を用いる全てのユーザは,共通のセキュリティパラメータ n , k , t {\displaystyle n,k,t} を用いる. 暗号の原理は,鍵生成者アリスが,効率的な復号アルゴリズムが分かっている符号 C {\displaystyle C} を(何らかの線形符号の族から)選び,符号 C {\displaystyle C} を公開するが復号アルゴリズムは秘密に保つ,というものである.符号 C {\displaystyle C} の復号には,符号 C {\displaystyle C} の生成行列の知識だけではなく,符号の族から C {\displaystyle C} を選び出したときに用いたパラメータを必要とする.例えば,二元ゴッパ符号においては,復号にはゴッパ多項式とcode locatorsが必要である.したがって,アリスは適切に難読化された C {\displaystyle C} の生成行列を公開することができる. より具体的には,鍵は以下のように生成される. 文章: DES-X DES-X (DESX) はDES (Data Encryption Standard) から派生したブロック暗号の一種で、key whitening と呼ばれる技法を使って総当り攻撃への耐性を強化している。 元々のDESのアルゴリズムは1976年に策定されたもので、鍵長が56ビットであり、鍵のとりうる値は 2 個ある。このため、例えばアメリカ国家安全保障局 (NSA) などの政府機関が総当り攻撃を実行できるかもしれないという指摘があった。DESのアルゴリズムを実質的には変更せず、鍵長だけを大きくしたのがDES-Xで、1984年5月にロナルド・リベストが提案した。 このアルゴリズムは、1980年代末以降、RSAセキュリティのBSAFE暗号ライブラリに含まれている。 文章: 暗号史 1940年代、第二次世界大戦終了前後に開発が始まったプログラム可能な電子計算機(コンピュータ)の登場は機械式暗号の信頼性をさらに失速させる。コンピュータは自由にプログラムを設定でき、任意の機械式暗号をシミュレートできる上に暗号化・復号のスピードも桁違いで、暗号鍵を総当りで調べる、暗号文を統計処理して暗号鍵を推測する等、暗号解読の強力なツールとなる。初期のコンピュータにはコロッサスのように暗号解読を目的として開発されたものもある。 一方で1947年のトランジスタの発明、1958年の集積回路の発明など半導体技術の進歩は暗号にも大きな影響を与え、機械式では実現不可能な複雑なアルゴリズムでも実現可能になった。信頼性の高い暗号が、手軽に利用できるようになったのもコンピュータや半導体技術が出現してからである。 1970年代、ホルスト・ファイステルにより換字式暗号と転置式暗号を組み合わせた換字-転字暗号が提案され、DESの原型となるブロック暗号 Lucifer が誕生した。 文章: 秘話 NESTORへの反省から、代替としてVINSONと呼ばれる新たな音声暗号化装置ファミリーの開発が1971年から始まった。音声符号化方式として適応デルタ変調の一種のCVSD (Continuously Variable Slope Delta modulation) を用い、音声を16kbpsに符号化し暗号化を行う方式で、NESTORと比べ音質が良くなり、LSI技術を用いたため機器も小型軽量化され、無線回線経由で暗号鍵の更新 (OTAR, Over the Air Rekeying) が可能で暗号鍵の配布も簡単になり使いやすくなった。暗号化にはアメリカのNSAと英国のGCHQとで共同開発したSAVILLEアルゴリズムを使用した。この具体的なアルゴリズムや仕様は公開されていない。使用される鍵長は8ビットのパリティビットを含め128ビットだと予想されている。 VINSONファミリーとしてKY-57(車両/歩兵用)やKY-58(航空機用)などの暗号化装置が開発され、1970年代から1980年代にかけてNESTORを置き換えていった。 第二次世界大戦中、アラン・チューリングによる秘話装置ディライラの開発により音声暗号化装置のノウハウを獲得したイギリスは、アメリカと同様、戦後もデジタル方式の音声暗号化装置の開発を続けた。アメリカのKO-6やKY-9等の初期の暗号化装置はSIGSALYの技術を受け継ぐアナログ方式のボコーダーを使い、無理な情報の圧縮を行っていたため音質の悪さに苦労していた。それに対しイギリスでは、ディライラと同じように音声を直接サンプリングして暗号化する広帯域の音声暗号化装置の開発を進めた。 1954年にイギリス陸軍がフィールド試験を行った音声暗号化装置 BID/100 (Hallmark) はそのような装置の1つである。"BID"は"British Inter Departmental"の頭文字で、機器がイギリスの複数の政府機関や部門で使用されうることを意味する。第二次世界大戦中にチューリングがエニグマ暗号の解読に従事したGC&CS(政府暗号学校、ブレッチリーパーク)は戦後GCHQ(政府通信本部)に改編され諜報や暗号関係の活動を行っており、"BID"機器はこの1部門であるCESG(コミュニケーションエレクトロニクスセキュリティグループ)が管轄している。 文章: 格子暗号 格子暗号 (あるいは格子ベース暗号) とは、方式自体あるいは安全性証明において格子を用いる暗号プリミティブを示す一般的用語である。格子ベースの暗号方式 (公開鍵暗号方式や鍵共有方式) は現在、耐量子暗号(英語版)の重要な候補となっている。広く利用されている公開鍵方式である RSAや 楕円曲線暗号、ディフィー・ヘルマン鍵共有は、量子コンピュータ上で実行できるショアのアルゴリズム(英語版)によって破られるが、いくつかの格子暗号は古典コンピュータと量子コンピュータの両方に対して攻撃耐性があると考えられている。さらに、多くの格子ベースの方式は、良く研究されている何らかの格子問題(英語版) (格子に関連した問題) が効率的に解けないという計算量的な仮定のもとで、安全であると考えられている。 文章: International Data Encryption Algorithm IDEAのブロック長は64ビットで、128ビットの鍵を使う。ラウンドと呼ばれる同じ操作を8回行い、最後に出力段の変換(ハーフラウンド)を行う。暗号化と復号の工程はよく似ている。代数学的にある意味で「非互換」とも言える異なる群からの操作(加算や乗算の合同式、ビット単位の排他的論理和 (XOR) など)を次々に行うことで、IDEAのセキュリティが生じている。演算をより詳細に述べると、すべて16ビット単位に以下のような操作を行う。図にあるラウンドを8回繰り返した後、ハーフラウンドを最後に1回行う。ラウンドの出力は16ビットが4つ並んでいるが、このうち2番目と3番目を入れ替え、右から順に以下の操作を行う。各ラウンドでは6個の16ビット部分鍵を使い、ハーフラウンドでは4つの部分鍵を使う。8.5ラウンドの合計で52個の部分鍵を使うことになる。最初の8個の部分鍵は元の鍵から直接取り出す。 文章: Cramer-Shoup暗号 Cramer-Shoup暗号(クレーマー シュープあんごう)とは暗号理論における暗号方式の一つ。適応的選択暗号文攻撃(英語版)に対する安全性(IND-CCA2)が標準モデル(暗号理論)(英語版)で証明された初の効率的な公開鍵暗号である。 安全性はDDH仮定(英語版)の計算理論的な非展性(但し証明はされていない)に基づいている。 1998年にロナルド・クレーマー(英語版)とビクター・シュープ(英語版)によって提案されたもので、ElGamal暗号の拡張になっている。 ElGamal暗号は頑強性を持たないが、Cramer-Shoup暗号は別の要素を加えることでより強力な攻撃者に対しても頑強性を達成している。 この頑強性は万能一方向ハッシュ関数の利用とElGamal暗号にはない計算の追加によって得られており、その結果、暗号文の長さはElGamal暗号の2倍になる。 文章: マンチェスタ符号 符号名称の由来は、マンチェスター大学で開発されたコンピュータ・Manchester Mark Iにおいて、磁気ドラムメモリにデータを保存する方式として使用されたことによる。この用途では位相符号化(PE方式)の名称で1600bpiの磁気テープによる磁気記録に広く使用されていたが、後に登場した6250bpiの磁気テープではマンチェスタ符号よりも効率的な群符号記録(英語版)が主流となっている。その後、マンチェスタ符号化は1990年代に10メガビット・イーサネット (IEEE 802.3)、2020年現在ではコンシューマIR(英語版)プロトコル、RFID、近距離無線通信などで広く使用されている。マンチェスタ符号では、各データビットを「高→低」「低→高」のいずれかで表現する。1ビットあたりに2つの信号レベルがあるため、Biphase(バイフェーズ, 二相)符号とも呼ばれる。 文章: IDベース暗号 ボネーとフランクリンはIDベース暗号方式を4つのアルゴリズムからなるものとして定義した。全体がうまく動作するためには、当り前ではあるが以下を前提とする。 ∀ m ∈ M , I D ∈ { 0 , 1 } : D e c r y p t ( E x t r a c t ( P , K m , I D ) , P , E n c r y p t ( P , m , I D ) ) = m {\displaystyle \forall m\in {\mathcal {M}},ID\in \left\{0,1\right\}^{*}:Decrypt\left(Extract\left({\mathcal {P}},K_{m},ID\right),{\mathcal {P}},Encrypt\left({\mathcal {P}},m,ID\right)\right)=m} 。 文章: International Data Encryption Algorithm International Data Encryption Algorithm (IDEA) はチューリッヒ工科大学の James Massey と来学嘉が設計し、1991年に発表したブロック暗号。DESの代替を意図したアルゴリズムである。IDEAは PES (Proposed Encryption Standard) を若干手直しした暗号であり、元々は IPES (Improved PES) と呼ばれていた。 この暗号は Hasler Foundation(後に Ascom-Tech AG に吸収された)との研究契約の下で設計された。多数の国で特許を取得しているが、非商用利用については自由に使うことが容認されていた。"IDEA" という名称は商標でもある。アメリカにおける特許の有効期限が2012年1月をもって失効したことで、全世界で自由に使うことができるようになった。 IDEAは Pretty Good Privacy (PGP) v2.0 で使われていた。これは、v1.0で使われていたBassOmaticが安全でないと判明したために導入されたものである。IDEAはOpenPGP規格ではオプションのアルゴリズムとされている。GNU Privacy Guard (GnuPG)では、特許の失効を受けて1.4.13/2.0.20から限定的にIDEAをサポートするようになった。 文章: ベル研究所 1940年代初め、Russell Ohl が光電セルを開発した。1943年、世界初のデジタル式音声暗号化システム SIGSALY を開発。これが第二次世界大戦中に味方同士の通信に利用された。また、真空管の6AK5はレーダーシステムに広く利用された。1947年、ジョン・バーディーン、 ウィリアム・ショックレー、ウォルター・ブラッテンがトランジスタを発明した(1956年、ノーベル物理学賞を受賞)。ベル研究所の最重要発明品と言われている。同年、リチャード・ハミングが誤り検出訂正のためのハミング符号を発明。特許が確定する1950年までその成果は公表されなかった。1948年、クロード・シャノンが情報理論の基礎を築いた "A Mathematical Theory of Communication" (通信の数学的理論)を Bell System Technical Journal に発表。ベル研究所の先達であるハリー・ナイキストやラルフ・ハートレーの業績を踏まえつつ、それらを大幅に発展させた。シャノンは1949年の論文 Communication Theory of Secrecy Systems で現代暗号論の基礎を築いた。 ベル研究所では、ジョージ・スティビッツらが1940年代にリレーを使った計算機をいくつも開発した。 1950年代は、本来の電話事業の技術的サポートにおける改良が主で、マイクロ波中継、オペレーターを介さない自動即時通話、中継局、電話通信用継電器 (wire spring relay)、新型交換機(5XB)などが登場した。1953年、モーリス・カルノーがカルノー図を開発。ブール代数式を扱いやすくするツールとして重宝された。1954年、世界初の実用的な太陽電池を開発した。1956年に敷設された初の大西洋横断海底ケーブル TAT-1(スコットランド-ニューファンドランド島間)は、AT&T、ベル研究所、イギリスとカナダの電話会社が関与した。1957年、マックス・マシューズが電子音楽演算用コンピュータプログラムMUSICを開発した。MUSICシリーズは現在の多くのコンピュータミュージックプログラムの基礎となった。ロバート・C・プリムとジョゼフ・クラスカル(英語版)が新たな貪欲法アルゴリズムを開発し、コンピュータネットワーク設計を進化させた。1958年、アーサー・ショーローとチャールズ・タウンズの学術論文で初めて「レーザー」なるものが紹介された。