暗号学者ではない私をいつも驚かせることの 1 つは、素数を使用することがなぜそれほど重要なのかということです。それらが暗号化においてそれほど特別な理由は何ですか?
誰か簡単な短い説明がありますか? （多くの入門書があり、応用暗号が聖書であることは承知していますが、前述のとおり、私は独自の暗号アルゴリズムを実装するつもりはありません。見つけたものは私の脳を爆発させました.10ページの数式はありません.お願いします ：））
すべての答えをありがとう。実際のコンセプトを最も明確にしてくれたものを受け入れました。
最も基本的で一般的な説明：暗号化はすべて数論に関するものであり、すべての整数（0と1を除く）は素数で構成されているため、数論では素数を多く扱います。
より具体的には、RSAなどのいくつかの重要な暗号化アルゴリズムは、大きな数の素因数分解に長い時間がかかるという事実に大きく依存しています。基本的に、メッセージの暗号化に使用される2つの大きな素数の積で構成される「公開鍵」と、メッセージの復号化に使用される2つの素数で構成される「秘密鍵」があります。公開鍵を公開することができ、誰もがそれを使用してメッセージを暗号化できますが、主要な要素を知っているのはあなただけであり、メッセージを復号化できます。数論の現在の最先端を考えると、他の誰もが数を因数分解する必要がありますが、これは実用的であるには時間がかかりすぎます。
単純？うん。
2つの大きな素数を掛けると、2つの（大きな）素因数だけを持つ巨大な非素数が得られます。
その数を因数分解することは重要な操作であり、その事実が多くの暗号化アルゴリズムのソースです。詳細については、一方向性関数を参照してください。
補遺：もう少し説明します。2つの素数の積は公開鍵として使用でき、素数自体は秘密鍵として使用できます。2つの要因のいずれかを知っていることによってのみ元に戻すことができるデータに対して行われた操作は、暗号化を解除するのに重要です。
これは非常に単純で一般的な例です。
安全なコマースWebサイトで一般的に使用されているRSA暗号化アルゴリズムは、2つの（非常に大きい）素数を取得して乗算するのは簡単ですが、その逆を行うのは非常に難しいという事実に基づいています。非常に大きな数であり、素因数が2つしかないため、それらを見つけます。
重要なのは素数そのものではなく、素数を扱うアルゴリズムです。特に、数 (任意の数) の約数を見つけます。
ご存知のように、任意の数には少なくとも 2 つの約数があります。素数には、1 とそれ自体の 2 つの因数があるという固有の性質があります。
因数分解が非常に重要な理由は、数学者やコンピューター科学者が、考えられるすべての組み合わせを単純に試してみないと因数分解する方法がわからないからです。つまり、まず 2 で割り、次に 3 で割り、次に 4 で割ります。素数、特に非常に大きな素数を素因数分解しようとすると、(本質的に) 2 からその大きな素数までの可能なすべての数を試す必要があります。最も高速なコンピューターでも、暗号化で使用される種類の素数を素因数分解するには数年 (場合によっては数百年) かかります。
暗号アルゴリズムに強みを与えるのは、大きな数を効率的に因数分解する方法がわからないという事実です。いつの日か誰かがその方法を見つけた場合、現在使用しているすべての暗号アルゴリズムは時代遅れになります。これはまだ未解決の研究分野です。
整数を素因数に因数分解する高速アルゴリズムを誰も知らないからです。それでも、素因数のセットが特定の整数に乗算されるかどうかを確認するのは非常に簡単です。
暗号化を強化するための優れたリソースがいくつかあります。これが1つです：
そのページから：
1977年にRonRivest、Adi Shamir、およびLen Adlemanによって発明された、最も一般的に使用される公開鍵暗号システムでは、公開鍵と秘密鍵の両方が、比較的単純な数式に従って大きな素数のペアから導出されます。理論的には、式を逆方向に実行することにより、公開鍵から秘密鍵を導出できる可能性があります。しかし、大きな素数の積だけが公開されており、そのサイズの数を素数に分解するのは非常に難しいため、世界で最も強力なスーパーコンピューターでさえ、通常の公開鍵を破ることはできません。
ブルースシュナイアーの本AppliedCryptographyは別のものです。その本を強くお勧めします。読書は楽しいです。
RSAが素数のプロパティをどのように使用するかについてもう少し具体的に説明すると、RSAアルゴリズムは、比較的素数「a」と「N」の場合、a^eは1モジュロNに一致するというオイラーの定理に大きく依存します。 eはオイラーのNのトーティエント関数です。
素数はどこから入りますか？Nのオイラーのトーティエント関数を効率的に計算するには、Nの素因数分解を知る必要があります。RSAアルゴリズムの場合、一部の素数「p」と「q」に対してN = pqである場合、e =（p --1）（q --1）= N --p --q + 1.しかし、pとqがわからないと、eの計算は非常に困難です。
より抽象的には、多くの暗号化プロトコルは、さまざまなトラップドア関数を使用します。これらの関数は、計算は簡単ですが、反転するのは困難です。数論はそのような落とし戸関数（大きな素数の乗算など）の豊富な情報源であり、素数は数論の絶対的な中心です。
私は本AMathematicalJourneyInCodeを提案します。この本は、暗号化に関するものであるため、驚くべきことに、地に足の着いた感じがします。この本は、子供の頃にパズルを学び、16歳でCayley-Purser（CP）アルゴリズムを作成するまでのサラ・フラナリーの旅をまとめたものです。一方向関数、数論、素数、およびそれらがどのように関連するかについて驚くほど詳細に説明しています。暗号化。
この本をあなたの質問にさらに具体的にしているのは、サラが行列を使用して新しい公開鍵アルゴリズムを実装しようとしたことです。素数を使用するよりもはるかに高速でしたが、それを悪用できる抜け穴が見つかりました。彼女のアルゴリズムは、プライベート暗号化メカニズムとしてより適切に使用されていたことがわかりました。この本は、時間の試練と非常に賢い個人の挑戦に耐えてきたので、暗号化に素数を使用することの素晴らしい証拠です。
あなたのためのもう一つのリソース。 今すぐセキュリティ！エピソード30（〜30分のポッドキャスト。リンクはトランスクリプトへのリンクです）では、暗号化の問題について説明し、素数が重要である理由を説明します。
私は数学者でも暗号学者でもないので、ここに素人の言葉での外部の観察があります (派手な方程式はありません、申し訳ありません)。
このスレッド全体は、素数が暗号でどのように使用されるかについての説明でいっぱいです。このスレッドで素数が使用される理由を簡単に説明する人を見つけるのは難しいです...おそらく、誰もがその知識を当然のことと思っているからです。
問題を外側から見るだけで、次のような反応が生じる可能性があります。しかし、それらが 2 つの素数の和を使用する場合、任意の 2 つの素数が生成できるすべての可能な和のリストを作成してみませんか?
このサイトには455,042,511の素数のリストがあり、最高の素数は9,987,500,000 ( 10桁) です。
知られている最大の素数 (2015 年 2 月現在) は、2 の 257,885,161 - 1 乗で、 17,425,170桁です。
これは、すべての既知の素数のリストを保持する意味がないことを意味します。数値を取り、それが素数かどうかを確認する方が簡単です。
大きな素数を計算すること自体が途方もない作業なので、相互に乗算された 2 つの素数を逆に計算することは、暗号学者と数学者の両方が十分に難しいと言うでしょう...今日。
暗号化アルゴリズムは、一般に、「困難な問題」を持つことにセキュリティを依存しています。最新のアルゴリズムのほとんどは、非常に大きな数の因数分解を難しい問題として使用しているようです。2つの大きな数を掛け合わせると、それらの因数の計算は「困難」（つまり時間がかかる）になります。これらの2つの数が素数である場合、答えは1つしかないため、さらに困難になります。また、答えを見つけたときに、同じ結果が得られる他の答えではなく、正しい答えであることが保証されます。
暗号化で重要なのは素数そのものではないと思いますが、素因数分解の難しさです
2つの素数mとnの積であることが知られている非常に大きな整数があるとすると、mとnが何であるかを見つけるのは簡単ではありません。RSAなどのアルゴリズムはこの事実に依存しています。
ちなみに、量子コンピューターを使ってこの素因数分解の問題を許容時間内に「解決」できるアルゴリズムに関する論文が発表されています。したがって、暗号化の新しいアルゴリズムは、量子コンピューターが登場したときに、素因数分解のこの「難しさ」にもはや依存しない可能性があります:)
素数は、与えられた数が素数であるかどうかを判断するのにかなりの時間を費やすため、主に暗号で使用されます。ハッカーにとって、アルゴリズムがコードを解読するのに多くの時間がかかる場合、それは彼らにとって役に立たなくなります