公開鍵暗号化

公開鍵暗号

対称キー暗号化とは異なり、公開キー暗号化の歴史的な使用は見当たりません。これは比較的新しい概念です。

対称暗号化は、政府、軍隊、および機密通信に関与する大規模な金融会社などの組織に適していました。

過去数十年でより安全ではないコンピューターネットワークが普及したため、より大規模な暗号化を使用するという真のニーズが感じられました。対称キーは、キー管理で直面した課題により、実用的ではないことがわかりました。これが公開鍵暗号システムを生み出しました。

暗号化と復号化のプロセスは、次の図に示されています-

公開鍵暗号化

公開鍵暗号化方式の最も重要なプロパティは次のとおりです-

暗号化と復号化には異なるキーが使用されます。これは、対称暗号化方式とは異なるこの方式を設定するプロパティです。
各受信者は、一般に自分の秘密キーと呼ばれる一意の復号化キーを所有しています。
受信者は、公開キーと呼ばれる暗号化キーを公開する必要があります。
このスキームでは、受信者としての攻撃者によるなりすましを回避するために、公開鍵の信頼性をある程度保証する必要があります。一般に、このタイプの暗号システムには、特定の公開鍵が特定の個人またはエンティティのみに属していることを証明する信頼できる第三者が関与します。
暗号化アルゴリズムは複雑で、攻撃者が暗号文と暗号化（公開）キーから平文を推測するのを防ぐことができます。
秘密鍵と公開鍵は数学的に関連していますが、公開鍵から秘密鍵を計算することは現実的ではありません。実際、公開キー暗号システムのインテリジェントな部分は、2つのキー間の関係を設計することです。

公開鍵暗号化スキームには3つのタイプがあります。私たちは次のセクションでそれらを議論します-

RSA暗号システム

この暗号システムは、初期システムの1つです。現在でも最も採用されている暗号システムです。このシステムは、3人の学者 Ron Rivest、Adi Shamir 、および Len Adleman によって発明されたため、RSA暗号システムと呼ばれています。

RSA暗号システムには、最初にキーペアを生成し、次に暗号化/復号化アルゴリズムの2つの側面があります。

RSAキーペアの生成

暗号化を使用した通信への参加を希望する各個人または当事者は、公開鍵と秘密鍵のペアのキーを生成する必要があります。キーの生成で従うプロセスは以下に説明されています-

* RSAモジュラス（n）*を生成します
2つの大きな素数pとqを選択します。 n = p qを計算します。強力で解読不能な暗号化の場合、nを大きな数値（通常は最小512ビット）にします。
派生番号の検索（e）
数値 e は1より大きく、（p − 1）（q − 1）未満でなければなりません。
1を除いて、eと（p − 1）（q − 1）に共通の因子があってはなりません。つまり、2つの数値eと（p – 1）（q – 1）は互いに素です。
公開鍵を作成
数字のペア（n、e）はRSA公開鍵を形成し、公開されます。
興味深いことに、nは公開キーの一部ですが、大きな素数の因数分解が困難なため、攻撃者はnの取得に使用される2つの素数（p＆q）を有限の時間で見つけることができません。これがRSAの強みです。
秘密鍵を生成
秘密鍵dは、p、q、およびeから計算されます。 nとeが与えられた場合、一意の番号dがあります。
数値dは、eモジュロ（p-1）（q – 1）の逆数です。これは、dが（p-1）（q-1）より小さい数であることを意味し、eを乗算すると1モジュロ（p-1）（q-1）に等しくなります。
この関係は次のように数学的に書かれています-

ed = 1 mod (p − 1)(q − 1)

拡張ユークリッドアルゴリズムは、p、q、およびeを入力として受け取り、dを出力として提供します。

例

RSAキーペアを生成する例を以下に示します。（理解を容易にするために、ここで取られる素数pとqは小さな値です。実際には、これらの値は非常に高いです）。

2つの素数をp = 7およびq = 13とします。したがって、モジュラスn = pq = 7 x 13 = 91です。
e = 5を選択します。これは有効な選択です。5の共通因子である数値はなく、1を除いて（p − 1）（q − 1）= 6×12 = 72です。
数字のペア（n、e）=（91、5）は公開鍵を形成し、暗号化されたメッセージを送信できるようにしたい人なら誰でも利用できるようにすることができます。
拡張ユークリッドアルゴリズムにp = 7、q = 13、e = 5を入力します。出力はd = 29になります。
計算することにより、計算されたdが正しいことを確認してください-

de = 29 × 5 = 145 = 1 mod 72

したがって、公開鍵は（91、5）であり、秘密鍵は（91、29）です。

暗号化と復号化

キーペアが生成されると、暗号化と復号化のプロセスは比較的簡単で、計算が簡単になります。

興味深いことに、RSAは、対称キー暗号化の場合のようにビット文字列を直接操作しません。 nを法とする数値で動作します。したがって、プレーンテキストをn未満の一連の数値として表す必要があります。

RSA暗号化

送信者が、公開キーが（n、e）である人にテキストメッセージを送信したいとします。
次に、送信者はプレーンテキストをn未満の一連の数字として表します。
nを法とする数値である最初のプレーンテキストPを暗号化します。暗号化プロセスは、単純な数学的ステップです-

C = Pe mod n

言い換えると、暗号文Cは、平文Pにeを掛けた値に等しく、nを法として減らされます。これは、Cもnより小さい数であることを意味します。
平文P = 10の鍵生成の例に戻ると、暗号文Cが得られます−

C = 105 mod 91

RSA復号化

RSAの復号化プロセスも非常に簡単です。公開鍵ペア（n、e）の受信者が暗号文Cを受信したと仮定します。
受信者はCを自分の秘密鍵の累乗に上げますd。 nを法とする結果は平文Pになります。

Plaintext = Cd mod n

数値の例に戻ると、暗号文C = 82は、秘密鍵29を使用して番号10に復号化されます-

Plaintext = 8229 mod 91 = 10

RSA分析

RSAのセキュリティは、2つの別個の機能の強度に依存します。 RSA暗号システムは、最も一般的な公開鍵暗号システムの強度であり、その強度は、非常に大きな数を因数分解するという実際的な困難に基づいています。

暗号化機能-これは、平文を暗号文に変換する一方向の機能と見なされ、秘密鍵dの知識がある場合にのみ元に戻すことができます。
キー生成-RSA公開キーから秘密キーを決定することの難しさは、モジュラスnを因数分解することと同等です。したがって、攻撃者は、nを因数分解できない限り、RSA公開鍵の知識を使用してRSA秘密鍵を決定することはできません。また、一方向関数であり、p＆q値からモジュラスnへの移行は簡単ですが、逆は不可能です。

これらの2つの機能のいずれかが一方向ではないことが判明した場合、RSAは機能しなくなります。実際、ファクタリングの効率的な手法が開発された場合、RSAは安全ではなくなります。

RSA暗号化の強度は、数pとqが大きな素数でない場合、および/または選択された公開鍵eが小さい場合、攻撃に対して大幅に低下します。

ElGamal暗号システム

RSAとともに、他の公開鍵暗号システムが提案されています。それらの多くは、離散対数問題の異なるバージョンに基づいています。

楕円曲線バリアントと呼ばれるElGamal暗号システムは、離散対数問題に基づいています。これは、特定の数の実際の時間枠では離散対数を見つけることができないという仮定から強度を導き出しますが、電力の逆演算は効率的に計算できます。

pを法とする数値で動作するElGamalの簡単なバージョンを見てみましょう。楕円曲線バリアントの場合、まったく異なる数体系に基づいています。

ElGamalキーペアの生成

ElGamal暗号システムの各ユーザーは、次のようにキーペアを生成します-

*大きな素数pの選択*通常、1024から2048ビット長の素数が選択されます。
ジェネレーター要素の選択g。
この数は1からp − 1の間でなければなりませんが、任意の数にすることはできません。
これは、pを法とする整数の乗法群の生成元です。これは、pと互いに素な整数mごとに、g ^ k ^ = a mod nとなるような整数kが存在することを意味します。 +たとえば、3はグループ5のジェネレータです（Z〜5〜= \ {1、2、3、4}）。

N	3ⁿ	3ⁿ mod 5
1	3	3
2	9	4
3	27	2
4	81	1

*秘密鍵の選択。*秘密鍵xは、1より大きくp-1より小さい任意の数です。
*公開鍵の一部を計算します。*値yは、次のようにパラメータp、gおよび秘密鍵xから計算されます-

y = gx mod p

公開鍵の取得 ElGamal公開鍵は、3つのパラメーター（p、g、y）で構成されています。 +たとえば、p = 17およびg = 6（6はグループZ〜17〜の生成元であることが確認できます）とします。秘密鍵xは、1より大きく71より小さい任意の数値にすることができるため、x = 5を選択します。その後、値yは次のように計算されます-

y = 65 mod 17 = 7

したがって、秘密鍵は62であり、公開鍵は（17、6、7）です。

暗号化と復号化

ElGamalキーペアの生成は、RSAの同等のプロセスよりも比較的簡単です。ただし、暗号化と復号化はRSAよりもやや複雑です。

ElGamal暗号化

送信者がElGamal公開キーが（p、g、y）である誰かに平文を送信したいとし、-

送信者は、pを法とする一連の数値として平文を表します。
pを法とする数として表される最初の平文Pを暗号化します。暗号文Cを取得するための暗号化プロセスは次のとおりです-
数値kをランダムに生成します。
2つの値C1およびC2を計算します。ここで-

C1 = gk mod p
C2 = (P*yk) mod p

2つの別個の値（C1、C2）で構成される暗号文Cを一緒に送信します。
上記のElGamalキー生成の例を参照すると、プレーンテキストP = 13は次のように暗号化されます-
ランダムに数値を生成します（k = 10など）
2つの値C1とC2を計算します。ここで-

C1 = 610 mod 17
C2 = (13*710) mod 17 = 9

暗号文C =（C1、C2）=（15、9）を送信します。

エルガマル復号

秘密鍵xを使用して暗号文（C1、C2）を復号化するには、次の2つの手順が取られます-
pを法とする（C1）^ x ^{のモジュラー逆行列を計算します。これは（C1）}-x ^で、一般に復号化係数と呼ばれます。
次の式を使用して平文を取得します-

C2 × (C1)-x  mod p = Plaintext

この例では、秘密鍵x = 5を使用して暗号文C =（C1、C2）=（15、9）を復号化するには、復号化係数は

15-5  mod 17 = 9

平文P =（9×9）mod 17 = 13を抽出します。

エルガマル分析

ElGamalシステムでは、各ユーザーは秘密鍵xを持っています。そして、公開鍵の* 3つのコンポーネント*-*素数モジュラスp、ジェネレータg、および公開Y = g ^ x ^ mod p *を持ちます。 ElGamalの強度は、離散対数問題の難しさに基づいています。

セキュアキーのサイズは通常、1024ビット以上です。今日では、2048ビット長のキーも使用されています。処理速度の面では、Elgamalは非常に遅く、主にキー認証プロトコルに使用されます。処理効率が高いため、ElGamalのElliptic Curveバリアントはますます普及しています。

楕円曲線暗号（ECC）

楕円曲線暗号（ECC）は、離散対数問題の特別なバージョンに基づいたセキュリティを備えた一連の暗号化ツールおよびプロトコルを記述するために使用される用語です。 pを法とする数値は使用しません。

ECCは、楕円曲線と呼ばれる数学的オブジェクトに関連付けられた数値のセットに基づいています。 pを法とする数の場合と同様に、これらの数の倍数を追加および計算するための規則があります。

ECCには、ElGamal暗号化やデジタル署名アルゴリズムなどのモジュラー番号用に最初に設計された多くの暗号化スキームのバリアントが含まれています。

離散対数問題は、楕円曲線上の点に適用した場合、はるかに困難になると考えられています。これは、pを法とする数値から楕円曲線上の点への切り替えを促します。また、楕円曲線ベースのバリアントを使用すると、短いキーでも同等のセキュリティレベルを取得できます。

短いキーは2つの利点になります-

キー管理の容易さ
効率的な計算

これらの利点により、暗号化スキームの楕円曲線ベースのバリアントは、コンピューティングリソースが制限されているアプリケーションにとって非常に魅力的です。

RSAとElGamalスキーム–比較

さまざまな側面でRSAとElGamalスキームを簡単に比較しましょう。

RSA	ElGamal
It is more efficient for encryption.	It is more efficient for decryption.
It is less efficient for decryption.	It is more efficient for decryption.
For a particular security level, lengthy keys are required in RSA.	For the same level of security, very short keys are required.
It is widely accepted and used.	It is new and not very popular in market.

Cryptography-public-key-encryption

目次

公開鍵暗号化