エンジニアリング哲学：Adi Shamir

要点

• 彼は、初の実用的な公開鍵暗号方式RSAの「S」です。 Ron Rivest、Leonard Adlemanとともに、Adi Shamirは1977年にMITでRSAを共同発明しました——同年に公に説明され、1978年2月にCommunications of the ACMで発表されています。この方式によって、事前に秘密を共有することなく、相手に宛てて暗号化し、その署名を検証できるようになりました。その安全性は、大きな数を素因数分解することの難しさに支えられています。この業績により、3人は2002年のACMチューリング賞を受賞しました。¹²
• 彼は、ひとつの多項式を完全な秘密へと変えました。 1979年、Shamirは「How to Share a Secret」を発表しました。これは秘密をn人で分け合い、そのうち任意のk人が集まれば復元でき、k-1人では何ひとつ——手がかりも、絞り込みすらも——分からないようにするしきい値方式です。すべては、多項式上の点だけから組み立てられています。³
• 彼は稀代の暗号解読者であり、守るために攻めます。 1980年代後半、Eli Bihamとともに、Shamirはブロック暗号を破る一般的な手法である差分解読法を公に発見しました。さらにそれ以前には、Merkle-Hellmanナップサック暗号も破っています。RSAを築いたのと同じ頭脳が、何十年もかけて物事を破る術を学んできました。暗号の世界では、それこそがシステムの強さを知る唯一の誠実な方法だからです。⁴⁵
• 彼は、清らかな数学を実用的な仕組みへと変え続けています。 RSAと秘密分散にとどまらず、ShamirはFiat-Shamir変換——ハッシュ関数を使って対話的証明を非対話的な署名に変える手法——を共同で考案し、ID ベース暗号や視覚暗号の方式も生み出しました。1980年からワイツマン科学研究所の教授を務める彼の経歴は、深遠な数論が博物館の展示物ではなく道具箱であることを示し続ける、長い論証なのです。¹⁶

原則

「のちに明らかになったのは、差分解読法がIBMと国家安全保障局（NSA）の双方によってすでに知られ——そして秘密にされていた——ということだった。」 ——BihamとShamirが公の場で再発見した手法について、歴史的記録を言い換えて⁴⁵

エンジニアリングの大半は、デモに向かって組み立てられます。書いて、動かして、動けば、その動作こそが証明です。ところが暗号はその安らぎを拒みます。正しく暗号化し復号する暗号は、それが安全かどうかについて何も示していません——破られた暗号と破られない暗号は、誰かが攻撃するまでまったく同じように振る舞うのです。だからこの分野は、別の真実の基準を発明せざるを得ませんでした。システムが信頼に値するのは、それが動くときではなく、本気の人々が懸命に破ろうとして失敗したときなのです。Shamirの経歴そのものが、この基準の体現です。システムを安全にするには、システムを破る術を学ぶ——守るために攻めるのです。⁴

最も明快な表れは、彼が両方の役割を自ら担っていることです。彼は公開鍵暗号の礎であるRSAを築き、証明可能な情報理論的安全性をもつShamirの秘密分散を築きました。¹³ しかし同時に、彼はMerkle-Hellmanナップサック暗号——安全に見えて実はそうでなかった対抗馬の公開鍵方式——も破り、データ暗号化標準（DES）そのものを脅かすほど一般的な手法である差分解読法を共同で発見しました。⁴⁵ これは2つの経歴ではありません。ひとつの規律です。構築の仕事は何が可能かを教え、破壊の仕事は何が本物かを教えます。築くだけの暗号研究者は当て推量をしているにすぎません。その最も背筋の凍る証拠が、のちに現れました。IBMとNSAは1970年代半ばから差分解読法を知っていながら機密扱いにしていた——つまり、公の分野は、敵がすでに手にしていた攻撃に対して目隠しのまま暗号を築き続けていたのです。⁴⁵

この原則にはもうひとつの半面があります。より静かですが、同じくらい重みを支えるもの——清らかな数学の着想を、実用的な仕組みへと変える力です。秘密分散はただの多項式補間にすぎません——2点が直線を、3点が放物線を定めるという、誰もが代数で出会う事実です。Shamirは、この同じ事実を逆から読めば、それがセキュリティの基本要素になると見抜きました。点を配れば、十分な数が集まるまで曲線は隠れたままなのです。³ RSAはただのべき剰余と素因数分解の困難さです。² Fiat-Shamir変換はただ検証者のコイン投げをハッシュに置き換えるだけです。⁶ 清らかな数学的構造を見つけ、それを仕組みとして読むこと。 真の冴えとは、新しい数学であることはまれです——それは、正しい角度から眺めれば、古い数学がすでにあなたの築きたいものそのものになっている、と見抜くことなのです。

背景

Adi Shamirは1952年7月6日、イスラエルのテルアビブで生まれました。¹ 1973年にテルアビブ大学で数学の学士号を取得し、その後ワイツマン科学研究所の大学院に進み、1975年に計算機科学の修士号、1977年に博士号を得ました。¹ 彼のめぐり合わせは、この分野そのものと同じく、まさに転換点を迎えようとしていました。1977年は、公開鍵暗号が心をくすぐる着想から動くシステムへと変わった年だったのです。

博士号取得後、彼はイングランドのウォーリック大学で1年間、博士研究員を務め、それからマサチューセッツ工科大学へ移り、1977年から1980年まで研究スタッフとして在籍しました。¹ RSAが生まれたのはMITです。暗号研究者であったRon Rivestは、共有された秘密なしに2者が秘匿性を確立できるというDiffie-Hellmanの着想に触発され、公開鍵方式を追い求めていました。ShamirとAdlemanは彼の協力者であり、そして決定的に、彼の敵対者でした——Rivestが方式を提案すると、ShamirとAdlemanがそれを破る。これを何度も何度も、ひとつが生き残るまで繰り返したのです。生き残ったのがRSAで、3人の名にちなんで名づけられ、1977年に公表、1978年にCommunications of the ACMで発表されました。² （彼らの知らぬところで、GCHQの英国人数学者Clifford Cocksが1973年の機密文書で等価なシステムを記述しており、それは1997年まで秘匿されたままでした——情報機関が見守るなか、公の分野が暗闇のなかで築いていた、もうひとつの実例です。）²

1980年、Shamirはワイツマン科学研究所へ戻り、以来そこで計算機科学・応用数学部門の教授を務め、のちにはパリの高等師範学校でも招聘教授職を兼ねました。¹ 彼を特徴づけるものはほとんどすべて——秘密分散、ナップサック暗号への攻撃、教え子Eli Bihamとの差分解読法、Fiat-Shamir変換、Moni Naorとの視覚暗号、キューブ攻撃、TWIRLとTWINKLEという素因数分解装置——ワイツマンから生まれました。2002年、米国計算機学会はRivest、Shamir、Adlemanの3人に、公開鍵暗号への貢献に対して、計算機科学の最高の栄誉であるチューリング賞を授けました。¹²

仕事

Shamirの秘密分散——秘密を守る放物線

ここから始めましょう。これは原則を最も純粋で、最も美しい形で示すものだからです。あなたに秘密があるとします——マスターキー、発射コード、宝庫のパスワード——そしてそれを5人の受託者で分け合い、そのうち任意の3人が一緒になれば復元でき、しかし2人では何も分からないようにしたい。鍵を物理的に切り分けようとしてもよいですが、それでは漏れてしまいます。断片それぞれが推測の幅を狭めてしまうからです。1979年の「How to Share a Secret」におけるShamirの洞察は、多項式がすでにこれを正確に解いている、というものでした。³

その仕掛けは、小学校で習う事実を逆から読みます。2点は唯一の直線を定め、3点は唯一の放物線を定める。一般に、k個の点は次数k-1の唯一の多項式を定めます。そこで、秘密をn人でしきい値kのもとに分け合うには、秘密をランダムな次数(k-1)の多項式の定数項——曲線のx = 0における値——として隠し、各人にその曲線上の1点を渡します。³ そのうち任意のk人は、自分たちの点を通る唯一の曲線を補間し、ゼロにおけるその値を読み取れます。けれども、驚くべきはその安全性です。k-1個の点しかなければ、曲線は見つけにくいどころではありません——本当に定まらないのです。あり得るどの秘密の値に対しても、彼らの点を通り、ゼロでその値をとる正しい次数の曲線が、ちょうどひとつ存在します。Shamirの方式が保証するように、「任意のk-1個以下のシェアを知っていても、Sはまったく定まらないままである」のです。³ しきい値に満たなければ何も明かさず、しきい値に達すればすべてを明かす。その清らかな、全か無かの境界こそが、この方式を情報理論的に安全にしているのです——破るのが計算的に難しいからではなく、そもそも情報がそこに存在しないから安全なのです。³

なぜこれがエンジニアリングとして重要なのか。この方式は、Shamirが数学を仕組みとして読む典型例です。彼は多項式補間を発明したわけではありません——それは何世紀も前からあるものです。彼が見抜いたのは、その失敗の様態——少なすぎる点からは曲線を復元できないこと——がまさにセキュリティの性質であり、その成功の様態——十分な点が曲線をぴたりと定めること——がまさに復元の性質である、ということでした。同じ事実が、両方向に使われることで、暗号の基本要素になります。それは今日、ハードウェアセキュリティモジュール、暗号資産の保管、認証局のなかで動いています。清らかな数学を、道具として読む。³

RSA——見知らぬ相手に向けて暗号化する

RSAは、ほとんど逆説的に思える問いに答えました。一度も会ったことがなく、敵が聞き耳を立てている回線越しにしか通信できない2人が、どうやって秘密をやり取りできるのか。古典的な暗号は、事前に確立された共有鍵を必要としました——しかし、まさに守ろうとしているその通信路の上で、鍵を共有することはできません。Rivest、Shamir、Adlemanが1977年に動くシステムへと組み上げた突破口は、落とし戸付き一方向関数でした。順方向には計算しやすく、逆方向には——秘密の情報を握っている場合を除いて——実行不可能な演算です。²

RSAの落とし戸は素因数分解です。2つの大きな素数を選んで掛け合わせ、法nをつくります。nと公開指数があなたの公開鍵になり、これは世界中に公表できます。誰でもそれを使い、べき剰余によってあなたに宛てたメッセージを暗号化できます。ところが復号には秘密鍵が必要で、それは元の2つの素数からしか導けません——そしてその積から元の素数を取り戻すには、非常に大きな数を素因数分解しなければならず、これは効率的な解法が知られていない問題なのです。² 定式化が述べるように、鍵を構成することは実用的である一方、「eとnだけが与えられたとき、法nにおけるe乗根を計算することは実行不可能」です。² あなたは錠前を公開し、鍵だけを自分で握る。そして両者の隔たりこそが、素因数分解の難しさなのです。

Shamirが果たした具体的な役割は、はっきり述べる価値があります。それがまさに、あの原則だからです——彼はAdlemanと並んで、この3人組の暗号解読者でした。RSA発明の物語は、破ることの物語です——Rivestが候補となる方式を提案し、ShamirとAdlemanがそれを攻撃し、ただひとつが攻勢に耐え抜くまで続けました。生き残った方式が強かったのは、まさにそれを破ろうと決意した2人の攻撃を耐え抜いたからこそです。RSAは、安全になるよう設計され、そうあってほしいと願われたシステムではありません。それは、自らの作者の攻撃を生き残ることで、その主張を勝ち取ったシステムなのです。²

守るために攻める——ナップサックを破り、差分解読法へ

RSAがShamirの築く姿を示すなら、次の一連の仕事は、この分野がそれ以上に必要とすることを彼がやってのける姿を示します——破ることです。1970年代後半、Merkle-Hellmanナップサック暗号はRSAの有力な対抗馬で、その安全性はNP完全である「部分和」問題に支えられ、それゆえ恐ろしく難しく見えました。Shamirはそれを破りました。Merkle-Hellmanが用いた特定のナップサックは、難しい一般のケースではなく、効率的に解ける特殊で構造化されたものにすぎないと示し——多くの人が信頼していた方式を打ち崩したのです。¹ そこにある教訓は、暗号が何度も学び直すものです。ある問題が一般には難しいからといって、あなたの暗号が実際に使うその個別の事例が難しいとは限りません。その違いを明らかにするのは、攻撃だけなのです。

彼の最も影響力のある暗号解読の仕事は、1980年代後半、教え子のEli Bihamとともに生まれました——差分解読法で、1990年ごろに発表されました。⁴⁵ これは、暗号への入力対の差が、出力の差へとどう伝播するかを調べる一般的な手法です。ある入力差が、無作為とは異なる確率である出力差をもたらすなら、その統計的な偏りはひび割れ——鍵についての情報の漏れ——です。BihamとShamirはそれを、当時世界で最も重要な暗号であったデータ暗号化標準（DES）の理論的弱点を含め、さまざまなブロック暗号への攻撃へと仕立て上げました。⁴⁵

そして、この分野は身の引き締まる事実を学びました。1994年、Don Coppersmithが明らかにしたのは、1970年代にDESを設計したIBMが「早くも1974年には」差分解読法を知っており、それへの防御がDESの明示的な設計目標であったこと、そしてNSAがこの手法を機密扱いにするよう迫ったこと——「設計上の考慮事項を開示すれば、多くの暗号に対して使える強力な手法である差分解読法の技術が明かされてしまう」からでした。⁴⁵ バックドアを隠していると長く疑われていたDESの謎めいた内部定数は、実は、公には存在すら知られていなかった攻撃に対する防御を隠していたのです。この一件は、Shamirの原則を支える、考えうる限り最も強力な論拠です。20年にわたって、開かれた共同体は暗号を築き信頼してきました——敵がすでに手にしていた根本的な攻撃に目隠しのまま。BihamとShamirによる公の再発見は、暗号を弱めはしませんでした——むしろ強めたのです。攻撃を光のもとへ引きずり出し、誰もがそれに対して設計できるようにしたのですから。守るために攻める、それを分野全体の規模で行ったのです。⁴⁵

Fiat-Shamirと、道具箱の広がり

同じ本能——清らかな構造を見つけ、それを仕組みとして読む——が、Shamirのほかの発明にも貫かれています。1980年代半ば、Amos Fiatとともに生み出したFiat-Shamir変換は、対話的な知識証明にまつわる実用的な問題を解きました。そうした証明は、検証者がランダムな挑戦を送り、証明者が応答するという、その場でのやり取りを必要とします。FiatとShamirは、検証者の唯一の役目が予測不可能なランダム性を供給することだと見抜き、証明者自身のメッセージに暗号学的ハッシュ関数を適用すれば、そのランダム性を同じように供給できると気づきました——会話を、ひとつの自己完結した非対話的な証明、すなわちデジタル署名へと変えたのです。⁶ あのひとつの変換が、現代の署名方式とゼロ知識システムの大きな部分を支えています。彼はまた、ID ベース暗号（人の身元をその公開鍵として使う）を提案し、Moni Naorとともに視覚暗号——画像を複数の透明シートに分割し、重ね合わせたときだけ秘密が現れる、目に見える秘密分散——を共同で考案し、のちにはキューブ攻撃やTWIRL・TWINKLEという素因数分解装置を発展させました。¹ そのすべてを通じて、同じ型が保たれています。既知の数学の一片が、正しい向きに回されることで、道具になるのです。

手法

RSA、秘密分散、破られたナップサック、差分解読法、そしてFiat-Shamirを横断して読むと、同じ信条が繰り返し現れます。Shamirの手法は、標語というより、一連の確たる習慣です。

同じ手で築き、破る。 その決定的な動きは、システムを構築する者と攻撃する者のあいだの分業を拒むことです。Shamirは RSA を共同発明し、かつ Merkle-Hellmanナップサックを破りました。秘密分散の安全性を証明し、かつ 差分解読法を共同で発見しました。この教訓は、暗号をはるかに超えて応用が利きます——自分が築いたものを本気で打ち負かそうと試みるまで、あなたはそれを理解してはいないのです。それは生き方にまで高められた証拠の関門です——「動く」は安全性の証拠ではなく、「本気の人々が破ろうとして、できなかった」が証拠なのです。²⁴

攻撃を生き残ったものだけを信じる。 ただ慎重に設計されただけの暗号は、希望にすぎません。集中的な暗号解読に耐え抜いた暗号は、事実です。規律とは、自分のシステムを、攻撃されるまでは有罪と見なすこと——ひびがあると仮定して探しに行くこと、敵が代わりに見つけてくれるのを待つのではなく、です。これはThompsonの「Reflections on Trusting Trust」の暗号における形です——敵対的に検めていないものは信頼できない、なぜなら見えない脅威こそがあなたをやられる脅威だから、という創始の洞察です——差分解読法の機密の歴史が証明したとおりに。⁴⁵

数学を仕組みとして読む。 最も強力な基本要素は、新しい数学であることはまれです。それは、新しい角度から見た古い数学です。多項式補間は秘密分散になり、素因数分解の困難さは落とし戸になり、ハッシュ関数は対話的な検証者の代役になります。習慣とは、清らかな構造を眺めて「これは何か」ではなく「これは何ができるか」と問うこと——最も強力な基本要素を最も単純なものでもあらしめる、あの手段の倹約であり、最小限の価値ある製品の精神に通じます。³⁶

得られるところでは証明可能な安全性を、それ以外のところでは勝ち取った安全性を選ぶ。 秘密分散は情報理論的に安全です——どれほど強力な計算機でも、少なすぎるシェアから秘密を取り出すことはできません。情報がそこに存在しないからです。³ RSAは計算的に安全です——素因数分解が難しいままである限りにおいてのみ安全です。Shamirは両方の水準で仕事をし、自分がどちらを手にしているかを正確に語ります。規律とは、自分のセキュリティの主張が何の上に立っているかを正確に知ること、そして「まだ誰も破っていない」を「破れない」と決して取り違えないことです。それは、信頼に適用された品質こそが唯一の変数です——数えるに値する唯一のものは、その保証が本物かどうかなのです。²³

一般のケースのなかに潜む特殊なケースを疑う。 Merkle-Hellmanを破ったことが、この分野に教えたのは、問題が一般にはNP完全であることは、暗号が実際に使う特定の事例について何も語らない、ということでした。¹ 確たる習慣とは、難しい問題の都合のよい構造化された版——システムを組み立てられるほど易しい版——こそが、まさに破りやすい版かもしれないと疑うことです。それは、Leslie Lamportが分散システムに持ち込んだのと同じ懐疑です——あなたが仮定した性質を信じてはならない。それが実際に成り立つ正確な条件を見つけ出すのです。

影響の連鎖

彼を形づくった人々

Diffie、Hellman、そして公開鍵の着想。 RSAは、事前共有鍵なしに秘匿性を確立できるとした、Whitfield DiffieとMartin Hellmanの1976年の提案への直接の応答でした。Diffie-Hellmanが問いを立て——公開鍵暗号方式は存在するはずだ——Rivest、Shamir、Adlemanが初の実用的な答えを築いたのです。²（直接の影響）

Ron RivestとLeonard Adleman。 RSAの共同研究は、まさに3人がかりでした——飽くなき提案者のRivest、飽くなき破り手のShamirとAdleman。提案し、攻撃し、繰り返す——その敵対的な構造をもつ協働関係が、構築と暗号解読はひとつの規律であるというShamirの生涯の信念を形づくりました。²（形成的な影響）

数論の伝統。 Shamirの真骨頂——古典数学を暗号の仕組みとして読むこと——は、数論、素因数分解の困難さ、有限体の代数を計算へと結びつける長い伝統の系譜にあります。彼の冴えは、その数学の発明ではなく、応用にありました。（形成的な影響）

彼が形づくった人々

Eli Bihamと現代の暗号解読。 教え子Bihamとともに発展させた差分解読法は、いまや本気のブロック暗号設計者が誰しも防御せねばならない標準的な道具となりました——高度暗号化標準（AES）の設計基準を含め、暗号の築かれ方そのものを作り替えたのです。⁴⁵

公開鍵のエコシステム全体。 RSAは、何十年にもわたる安全な通信、デジタル署名、鍵交換を支えてきました。ブラウザが安全な接続を確立するたび、証明書を検証するたび、それはShamirが築くのを助けた公開鍵の基盤の上に立っています。²

ゼロ知識と署名の方式。 Fiat-Shamir変換は、現代の幅広いデジタル署名とゼロ知識証明システムの土台で働く立役者です——いまやプライバシー保護やブロックチェーン暗号の中核をなすものも含めて。⁶

貫く糸

Shamirは、この連載におけるセキュリティの要石です——残りのスタック全体を信頼に値するものにする人物です。Tim Berners-Leeは誰もが使えるウェブを築きましたが、買い物をし、銀行取引をし、自由に発言できるウェブは、そのTLS接続と署名付き証明書を、公開鍵暗号にまったく依存しています——つまり、RSAと、Shamirが創設を助けた分野に依存しているのです。ThompsonとRitchieは、私たちが動かすシステムを与え、そして「Reflections on Trusting Trust」において、敵対的に検めていないものは信頼できないという創始の警告を与えました——まさにShamirが一生をかけて築いた本能です。そしてLeslie Lamportは分散システムに、正しさを正確に定義しそれを証明する規律を、任意に振る舞うビザンチン的な敵に抗して与えました。Shamirの秘密分散は、その同じ衝動の暗号における形であり、希望ではなく証明をもった基本要素です。Berners-Leeがこれは誰のためのものだと言い、Thompsonが自分で築いていないものは何も信じるなと言うのに対し、Shamirはこう言います——私はあなたのために安全なものを築こう。そして、それを破ろうと一生を費やそう——それこそが、私たちのどちらにとっても、それが本物だと知る唯一の方法だからだ、と。（連載の架け橋）

ここから受け取るもの

私がShamirから持ち帰り続ける教訓は、攻撃を生き残ったものだけを信じるということです。私の本能は、たいていの作り手と同じく、動くコードを証明と見なすことです——テストが通り、デモが走れば、出荷だ、と。暗号はその安らぎを禁じます。破られたシステムと健全なシステムは、誰かが攻撃するまでまったく同じに見えるからです。そしてShamirの答えは、自分がまずその誰かになることでした。彼はナップサック暗号を破り、Adlemanとともに RSA が生き残るまでRivestの候補方式を破り、Bihamとともに、情報機関が20年隠してきたものを暴くほど手ひどくDESを破りました。だから私はいま何かを築くとき——認証フロー、権限の境界、データパイプライン——攻撃者が来る前に、自分が攻撃者の帽子をかぶろうとします。ひびがあると仮定して狩りに出る、教えられるのを待つのではなく。意味のある自信とは、「どう壊れるか見えない」ではありません。「本気で破ろうとして、できなかった」なのです。

第二の教訓は、最も強力な仕組みは、正しい向きに読まれた清らかな数学であるということです。秘密分散は、初めて理解したとき、私を少し打ちのめしました——それはただ、点が多項式を定めるという教科書の事実にすぎないのに、それでいて、証明可能で情報理論的に安全な秘密を生み出すのです。Shamirはより難しい数学を発明したわけではありません。すでに手にしていた数学が、ある角度から見ればまさにセキュリティの基本要素である、と見抜いたのです。それが、すでに目の前にある構造への私の見方を変えました。検索に使うハッシュは、コミットメントになり得る。信頼性のために加えた冗長性は、しきい値方式になり得る。厄介者として扱った制約は、錠前になり得る。技とは、いつも新しい何かを発明することではありません——すでに理解している清らかなものが、正しい向きに回せば、必要としていた仕組みそのものなのだと気づくことなのです。

FAQ

Adi Shamirは何で知られていますか？

Adi Shamirはイスラエルの暗号研究者でワイツマン科学研究所の教授であり、RSAの「S」として最もよく知られています——RSAは初の実用的な公開鍵暗号方式で、1977年にMITでRon Rivest、Leonard Adlemanとともに共同発明しました。3人はこの業績で2002年のACMチューリング賞を分かち合いました。彼はまたShamirの秘密分散（1979年）を発明し、Eli Bihamとともに差分解読法を共同で発見し、Fiat-Shamir変換を共同で生み出すなど、暗号への貢献は数多くにのぼります。¹²

Shamirの秘密分散とは何ですか？

これは、Shamirが1979年に「How to Share a Secret」で発表した、秘密をn人で分け合い、そのうち任意のk人が復元でき、k-1人では何も分からないようにする方法です。秘密は次数k-1のランダムな多項式の定数項として隠され、各人がその曲線上の1点を受け取ります。k個の点が次数(k-1)の多項式を一意に定めるので、任意のk個のシェアが秘密を復元します——一方、k個に満たなければ秘密は「まったく定まらない」ままで、この方式に情報理論的安全性を与えます。³

RSAの「S」とは誰で、RSAはどう動くのですか？

「S」はShamirです。RSAはRivest、Shamir、Adlemanの頭文字です。RSAは公開鍵暗号方式です。各利用者は、誰もがメッセージの暗号化や署名の検証に使える公開鍵と、本人だけが握る秘密鍵をもちます。その安全性は落とし戸に支えられています——公開鍵は2つの大きな素数の積から作られ、秘密鍵を取り戻すにはその積を元の素数へと素因数分解する必要があり、これは十分に大きな数では計算的に実行不可能なのです。RSAは1978年にCommunications of the ACMで発表されました。²

差分解読法とは何ですか？

差分解読法は、1980年代後半にEli BihamとAdi Shamirが公に発見した一般的な手法で、入力対のあいだの差が出力の差へとどう伝播するかを調べることで、ブロック暗号を攻撃します。その伝播における統計的な偏りは、秘密鍵についての情報を漏らし得ます。BihamとShamirはそれを使って、DESの理論的弱点を見つけました。のちに明らかになったのは、IBMとNSAが1970年代半ばからこの手法を知っており、機密扱いにし、それに耐えるようDESを密かに設計していた、ということでした。⁴⁵

出典