[Powered by Google Translate] [RSA]
[ロブボーデン] [トミーM​​acWilliam] [ハーバード大学]
[これはCS50です。] [CS50.TV]
のは、RSA、データを暗号化するために広く使われているアルゴリズムを見てみましょう。
シーザーとVigenère暗号のような暗号化アルゴリズムでは、非常に安全ではありません。
シーザー暗号を使用すると、攻撃者はわずか25の異なる鍵を試す必要があります
メッセージのプレーンテキストを取得します。
Vigenère暗号はシーザー暗号よりも安全ですが
なぜなら、一度のキーの大きな探索空間、攻撃の
Vigenère暗号のキーの長さは、知っている
れ、暗号化されたテキスト内のパターンの解析を介して決定することができます
Vigenère暗号は、そのはるかに安全なシーザー暗号以外ではありません。
RSAは、他の一方で、このような攻撃に対して脆弱ではありません。
シーザー暗号とVigenère暗号が同じキーを使用する
暗号化と復号化の両方へのメッセージ。
このプロパティでは、これらの暗号、対称鍵アルゴリズムを作る。
対称鍵アルゴリズムの基本的な問題
彼らはメッセージを暗号化して送るものに依存していることである
と1は、メッセージを受信して​​復号化する
すでに彼らは両方使用するキーに先行を合意しています。
しかし、我々はここで起動時の問題のビットを持っています。
どのように通信する2台のコンピュータは、それらの間の秘密鍵を確立するのですか？
鍵は秘密でなければならないなら、私たちは鍵を暗号化および復号化するための方法が必要です。
我々が持っているすべては、対称鍵暗号である場合
その後、我々はちょうど同じ問題に戻ってきました。
RSAは、その一方で、鍵のペアを使用しています
復号用の暗号化と別のもの。
一つは公開鍵と呼ばれ、もう一つは秘密鍵です。
公開鍵は、メッセージを暗号化するために使用されます。
あなたはその名前で察しのとおり、私たちは私たちの公開鍵を共有することができます
我々は暗号化されたメッセージのセキュリティを損なうことなく、誰でも欲しい。
公開鍵を使用して暗号化したメッセージ
唯一それに対応する秘密鍵で復号化することができます。
あなたの公開鍵を共有できますが、常にあなたの秘密鍵を秘密にしておく必要があります。
そして唯一の秘密鍵は、メッセージを復号化するために使用することができます
2ユーザーは、RSAで暗号化されたメッセージを送信したい場合は、
前後に両方のユーザーは、自分の公開鍵と秘密鍵のペアを持っている必要があります。
ユーザ1からユーザ2へのメッセージ
唯一のユーザ2からユーザ1にユーザ2の鍵のペア、およびメッセージを使用
唯一のユーザー1の鍵ペアを使用しています。
暗号化と復号化メッセージに2つの独立したキーが存在するという事実
RSA非対称鍵アルゴリズムになります。
我々は、別のコンピュータにそれを送信するために、公開鍵を暗号化する必要はありません。
キーはとにかく公開されているからです。
これは、RSAが同じ起動時の問題を持っていないことを意味
対称鍵アルゴリズムとして。
だから私は、RSA暗号化を使用してメッセージを送信したい場合
ロブには、私は最初にロブの公開鍵が必要になるでしょう。
鍵のペアを生成するには、ロブは2つの大きな素数を選ぶ必要があります。
これらの番号は、パブリックキーとプライベートキーの両方で使用されます
しかし、公開鍵のみが、これらの2つの数値の積を使用します
番号ではなく自分自身。
私はロブの公開鍵を使ってメッセージを暗号化したら
私はロブにメッセージを送ることができます。
コンピュータについては、ファクタリング番号は困難な問題である。
公開鍵は、覚えている、2素数の積を使用していました。
この製品は、その後、唯一の2つの要因を持っている必要があります
その秘密鍵を構成する数値であることが起こる。
メッセージを解読するために、RSAはこの秘密鍵を使用します
または番号は、公開鍵を作成する過程で一緒に乗算。
それは数を素因数分解するのは困難だから
秘密鍵で使用される2つの数値に公開鍵で使用
攻撃者が秘密鍵を把握するのは困難だ
それは、メッセージを復号化する必要があるだろう。
今度は、RSAのいくつかの低レベルの詳細に行くことができます。
まず、鍵のペアを生成する方法を見てみましょう。
まず、我々は2素数が必要になります。
我々は、これらの2つの数pとqと呼ぶことにします。
pとqを選択するためには、実際に我々が擬似乱数発生させるでしょう
次に大きな数字とは、かどうかを判定するためのテストを使用する
これらの数字は、おそらく素数である。
我々は何度も繰り返し乱数を生成維持することができます
我々は我々が使用できる2素数を持つまで。
ここのは、p = 23、Q = 43を選ぶことができます。
覚えておいて、実際には、pとqははるかに大きい数字でなければなりません。
私たちの知る限りでは、数値より大きい、難しくはある
暗号化されたメッセージを解読します。
しかし、それはまた、暗号化と復号化メッセージに、より高価です。
今日では、多くの場合、pとqは少なくとも1024ビットであることをお勧めします
これは、300以上の桁でそれぞれの番号を入れます。
しかし、我々はこの例のために、これらの小さな数字を選ぶでしょう。
今、私たちは、第三番号を取得するために一緒にpとqを掛けます
我々は、n呼びます。
私たちのケースでは、n = 23 989 = * 43。
我々は、n = 989を持っています。
qで - 1 - 1次の我々は、pを掛け'll
我々は、mを呼ぶことにします第四数を取得します。
私たちの場合、m = 22 924 = * 42。
我々は、m = 924を持っています。
今、私たちは、mと互いに素である数eが必要になります
とm未満。
2つの数字は相対的に素数または互いに素
両方均等に分割のみ正の整数が1である場合。
言い換えれば、eとmの最大公約数で
1でなければなりません。
eは素数65537であるためには、実際には、それが一般的です
ある限り、この数字は、mの因子であることが起こりません。
私達のキーの場合は、e = 5を選ぶでしょう
5以降924と互いに素である。
最後に、我々はDと呼ぶことにしますもう一つの数を、必要があります。
Dは方程式を満たすいくつかの値でなければなりませんデ= 1（mod m）を。
このmod mは、我々はモジュラ演算と呼ばれるものを使うことにします意味します。
モジュラー算術では、いったん数がいくつかの上限よりも高くなる
それが0に戻って周りに折り返されます。
クロックは、例えば、モジュラー演算を使用しています。
1：59 1分後には、例えば、2時です
1:60ません。
分針が0にラップアラウンドした
60の上限に到達したとき。
そこで、我々は60が0（MOD 60）と等価であると言うことができます
と125 65と同等である5（MOD 60）と等価である。
私たちの公開鍵は、ペアeとnとなります
この場合にはeが5であり、nは989です。
私たちの秘密鍵は、ペアDとNとなります
我々の場合にはこれは185と989です。
当社独自の素数pとqが表示されないことに注意してください
どこでも私たちのプライベートまたはパブリックキーインチ
今、私たちは私たちの鍵のペアを持っている、のは、我々は暗号化する方法について見ていきましょう
とメッセージを解読する。
私は、ロブにメッセージを送信したい
だから彼は、この鍵ペアを生成するには1になります。
その後、私は使用します、彼の公開鍵のためにロブを頼むよ
彼に送信するメッセージを暗号化します。
ロブは私と一緒に自分の公開鍵を共有するために覚えておいて、それは完全に大丈夫です。
しかし、それは自分の秘密鍵を共有しても大丈夫ではないでしょう。
私は自分の秘密鍵が何であるか、任意のアイデアを持っていない。
我々は、いくつかのチャンクに私たちのメッセージmを破ることができる
すべてはそれからnよりも小さいと、それらの断片のそれぞれを暗号化します。
我々は、我々は4チャンクに分割することができる文字列CS50を暗号化します
文字ごとに1。
私のメッセージを暗号化するために、私はにそれを変換する必要があります
数値表現のいくつかの種類。
私のメッセージで文字のASCII値を連結してみましょう。
与えられたメッセージmを暗号化するために、
私はe（mod n）とにc = mを計算する必要があります。
しかし、mがnよりも小さくなければなりません
あるいは完全なメッセージはmodulo nを表現することはできません。
我々は、nより小さいすべてのうちいくつかのチャンク、にメートルを破ることができる
そして、それらの断片のそれぞれを暗号化します。
これらのチャンクのそれぞれの暗号化、我々は得るC1〜5 = 67（MOD 989）
どちら= 658。
私たちの第2のチャンクのために私達は5（MOD 989）に83を持っている
どちら= 15。
我々の3番目のチャンクのために私達は5（MOD 989）〜53持っている
どちら= 799。
そして最後に、私たちの最後のチャンクに対して我々は5（MOD 989）〜48持っている
どちら= 975。
今、私たちはロブにこれらの暗号化された値を上に送信することができます。
ここでは、ロブに行く。
私たちのメッセージが飛行中であるが、のは別のを見てみましょう
どのように我々は、Dに対して、その値を得た。
我々の数dは5D = 1（MOD 924）を満足する必要がありました。
これは、D 5モジュロ924の逆数になります。
与えられた2つの整数であり、bは、拡張ユークリッドの互除法
これらの2つの整数の最大公約数を見つけるために使用することができます。
それはまた、私たちに、xとyを、他の2つの数字を与える
それはaとbの=最大公約数で方程式ax +を満たす。
これはどのように私たちを助けるのですか？
まあ、のためのe = 5を差し込む
aとbのm = 924
我々はすでにこれらの数字は互いに素であることを知っている。
それらの最大公約数は1である。
これは私達に5倍+ 924y = 1を与える
または5x = 1 - 924y。
しかし、我々は唯一のすべてモジュロ924を心配している場合
924y - それから私達はドロップすることができます。
クロックに戻って考えてみてください。
分針は1日で、その後正確に10時間では、合格した場合
我々は、分針がまだ1日になることを知っている。
ここでは、1から始まり、その後正確にy回包み込む、
そう、我々はまだ1時になるでしょう。
我々は、5倍= 1（MOD 924）があります。
そしてここでこのxは、我々の前に探していたdと同じです
我々は、拡張ユークリッドの互除法を使うので、もし
この数値xを得るために、それは私達が私達dとして使用する必要がある番号です。
今すぐ= 5のための拡張ユークリッドアルゴリズムを実行してみましょう
およびb = 924。
我々は、テーブル方式と呼ばれる方法を使うことにします。
私たちのテーブルには4列のx、y、d、およびKを持つことになります。
私たちのテーブルには2行から始まります。
最初の行では、その後、1、0、5での我々の価値を、持っている
そして我々の第二行は、​​0,1、および924はb、私たちの値です。
第四列の値、kは結果になるでしょう
dの値と、その上の行のdの値を分​​割する
同じ行にある。
我々は、924で割った5がいくつか残りは0である必要があります。
それは、我々は、k = 0を意味しています。
今では他のすべてのセルの値は、その上のセル2行の値になります
それ回K上の行の値を引いた。
第三行にdから始めてみましょう。
924 * 0 = 5 - 私たちは5になっています。
1 * 0 0です - 次に、我々は0を持っている
と1 - 1である0 * 0。
それほど悪くはないので、の次の行に移りましょう。
まず、kの我々の価値を必要としています。
いくつかの残りが5 = 184で割って924、
そうkのための私達の値は184です。
今すぐ924から5 * 184 = 4である。
1から0 * 184は1であり、0から1までは、* 184は-184です。
すべての権利は​​、次の行を実行してみましょう。
kの値は、私たちのために1になります
いくつかの残りは4 = 1で割った5。
他の列に記入しましょう​​。
5から4 * 1 = 1。
0から1 * 1 = -1。
と1から184 * 1は185です。
kの私たちの次の値がどうなるか見てみましょう。
我々は4である1で4を分け持っているようにまあ、それが見えます。
我々は1で割るいるこのケースではそのようなことkがに等しい
上の行にdの値は、我々は我々のアルゴリズムで行われていることを意味します。
我々は、我々が最後の行でx = 185とy = -1を持っていることをここに見ることができます。
現在、私たちの本来の目的に戻ってきましょう。
我々は、このアルゴリズムを実行した結果として、xの値と言った
（MOD b）の逆数となります。
185 5（MOD 924）の逆数であることを意味します
これは、我々はdの185の値を持つことを意味します。
事実d = 1の最後の行に
その電子がmと互いに素であったかどうかを検証します。
それが1でなかったならば、我々は新しい電子を選択しなければならないでしょう。
今ロブが私のメッセージを受け取ったかどうかを確認してみましょう。
誰かが私に暗号化されたメッセージを送信するとき
限り、私は私の秘密鍵を秘密に保たれてきたように
私はメッセージを解読することができるだけだ。
解読するチャンクcに私は元のメッセージを計算することができます
Dパワーにチャンク（mod n）と等しくなります。
dとnは私の秘密鍵からのものであることを覚えておいてください。
我々解読各チャンクのチャンクから完全なメッセージを取得するには
し、結果を連結します。
RSAは、正確にどのように安全ですか？
真実は、我々は知らない。
セキュリティは、それはメッセージを解読する攻撃を取るとどのくらいに基づいている
RSAで暗号化されます。
攻撃者は自分の公開鍵へのアクセス権を持っていることを忘れないでください、
これは、eとnの両方が含まれています。
攻撃者は、その2素数pとqにnを因数分解する管理している場合
それから彼女は、拡張ユークリッドの互除法を用いてdを計算することができる。
これは彼女にどんなメッセージを復号化するために使用することができる秘密鍵を与える。
しかし、どのようにすぐに我々は、整数を因数分解することができますか？
再び、我々は知らない。
誰も、それを行うための高速な方法を見つけていません
これは、十分な大きさn指定されたことを意味します
それは非現実的に長い攻撃を取るだろう
数を因数分解する。
誰かがファクタリング整数の高速な方法を明らかにした場合
RSAは破られるだろう。
しかし、素因数分解は本質的に低速であっても、
RSAアルゴリズムはまだそれにいくつかの欠陥を持っている可能性が
それは、メッセージを簡単に解読することができます。
誰も、まだこのような欠陥を発見したと明らかにした
しかし、それは1つが存在しないという意味ではありません。
理論的には、誰かがRSAで暗号化されたすべてのデータを読み取るそこにある可能性があります。
プライバシーの問題の別のビットがあります。
トミーは自分の公開鍵を使用して、いくつかのメッセージを暗号化した場合
そして、攻撃者は自分の公開鍵を使用して同じメッセージを暗号化し
攻撃者は、2つのメッセージが同一であることがわかります
したがって、トミーは暗号化され知っている。
これを防止するために、メッセージは、一般的にランダムビットで埋められます
同じメッセージが暗号化されたように、暗号化される前に
複数回メッセージのパディングが異なる限り、違って見えるでしょう。
しかし、我々はチャンクにメッセージを分割する必要がどのように覚えている
各チャンクはnよりも小さくなるように？
塊を水増しすることは我々は物事を分割する必要性があることを意味
さらにチャンクにパディングチャンクはnよりも小さくなければならないからです。
暗号化および復号化は、RSAと比較的高価である
と非常に多くのチャンクにメッセージを分割する必要があることは非常に高価なことができます。
大量のデータが暗号化されており、解読する必要がある場合
我々は、対称鍵アルゴリズムの利点を組み合わせることができます
RSAのものとし、セキュリティと効率の両方を取得します。
我々はここでそれには触れませんが、
AESはVigenèreとシーザー暗号のような対称鍵アルゴリズムです
クラックすることが、はるかに難しい。
もちろん、我々は共有秘密鍵を確立せずにAESを使用することはできません。
2システム間で、我々は前にその問題を見ました。
しかし、今、私たちは2つのシステム間の共有秘密鍵を確立するためのRSAを使用することができます。
我々は、データの送信者を送信しているコンピュータと呼ぶことにします
とコンピュータがデータを受信機を受信。
受信機は、RSA鍵のペアを持っており、送信する
送信者への公開鍵。
送信者は、AESキーを生成
レシーバのRSA公開鍵で暗号化し、
とレシーバにAESのキーを送信します。
受信機は、RSA秘密鍵でメッセージを復号化します。
送信者と受信者の両方が今、それらの間の共有のAESキーを持っています。
RSAより暗号化と復号化ではるかに高速であるAES、
今では、大量のデータを暗号化し、受信機にそれらを送信するために使用することができます
復号化に同じ鍵を使用できる人。
RSAより暗号化と復号化ではるかに高速であるAES、
今では、大量のデータを暗号化し、受信機にそれらを送信するために使用することができます
復号化に同じ鍵を使用できる人。
私達はちょうど共有鍵を転送するためにRSAを必要としていました。
私たちはもはや全くRSAを使用する必要はありません。
私がメッセージを持っているように見えます。
誰も私がそれをキャッチする前に、紙飛行機の上にあるものを読むかどうかは関係ありません
私は、秘密鍵でだけだからです。
メッセージ内のチャンクのそれぞれ解読してみましょう。
最初の塊、658、我々は、185であるd電源に引き上げる
989あるmod nを、67に等しいので、
これは、ASCIIの文字Cである。
さて、第2のチャンクにドラッグします。
第二チャンクは、値15を有している
我々は第百八十五べき乗、どの
モッズ989、これは83に等しい
これは、ASCIIの文字のSです。
値799を持つ第三塊のために今、私たちは、185に上げる
モッズ989、これは53に等しく、
ASCIIの文字5の値である。
今値975を持つ最後のチャンクに対して、
我々は、185にMOD 989を上げる
これは、ASCIIの文字0の値は48に等しい。
私の名前はロブ·ボーデンであり、これはCS50です。
[CS50.TV]
すべてのRSA。
すべてのRSA。 [笑い]
まったく。