[Powered by Google Translate] [RSA] [ロブボーデン] [トミーMacWilliam] [ハーバード大学] [これはCS50です。] [CS50.TV] のは、RSA、データを暗号化するために広く使われているアルゴリズムを見てみましょう。シーザーとVigenère暗号のような暗号化アルゴリズムでは、非常に安全ではありません。シーザー暗号を使用すると、攻撃者はわずか25の異なる鍵を試す必要がありますメッセージのプレーンテキストを取得します。 Vigenère暗号はシーザー暗号よりも安全ですがなぜなら、一度のキーの大きな探索空間、攻撃の Vigenère暗号のキーの長さは、知っているれ、暗号化されたテキスト内のパターンの解析を介して決定することができます Vigenère暗号は、そのはるかに安全なシーザー暗号以外ではありません。 RSAは、他の一方で、このような攻撃に対して脆弱ではありません。シーザー暗号とVigenère暗号が同じキーを使用する暗号化と復号化の両方へのメッセージ。このプロパティでは、これらの暗号、対称鍵アルゴリズムを作る。対称鍵アルゴリズムの基本的な問題彼らはメッセージを暗号化して送るものに依存していることであると1は、メッセージを受信して復号化するすでに彼らは両方使用するキーに先行を合意しています。しかし、我々はここで起動時の問題のビットを持っています。どのように通信する2台のコンピュータは、それらの間の秘密鍵を確立するのですか？鍵は秘密でなければならないなら、私たちは鍵を暗号化および復号化するための方法が必要です。我々が持っているすべては、対称鍵暗号である場合その後、我々はちょうど同じ問題に戻ってきました。 RSAは、その一方で、鍵のペアを使用しています復号用の暗号化と別のもの。一つは公開鍵と呼ばれ、もう一つは秘密鍵です。公開鍵は、メッセージを暗号化するために使用されます。あなたはその名前で察しのとおり、私たちは私たちの公開鍵を共有することができます我々は暗号化されたメッセージのセキュリティを損なうことなく、誰でも欲しい。公開鍵を使用して暗号化したメッセージ唯一それに対応する秘密鍵で復号化することができます。あなたの公開鍵を共有できますが、常にあなたの秘密鍵を秘密にしておく必要があります。秘密鍵は秘密とは、秘密鍵を保持しなければならないので、 2人のユーザがメッセージを送信したい場合は、メッセージを復号化するために使用することができます前後に、RSAで暗号化された両方のユーザーは、自分の公開鍵と秘密鍵のペアを持っている必要があります。ユーザ1からユーザ2へのメッセージは専用のユーザ2の鍵ペアを使用し、とユーザ2からユーザ1へのメッセージは、ユーザ1の鍵ペアを使用しています。暗号化と復号化メッセージに2つの独立したキーが存在するという事実 RSA非対称鍵アルゴリズムになります。我々は、別のコンピュータにそれを送信するために、公開鍵を暗号化する必要はありません。キーはとにかく公開されているからです。これは、RSAは対称鍵アルゴリズムと同じ起動時の問題を有していないことを意味する。通信する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。 [笑い] まったく。