はてなブックマーク

初めに 『暗号技術のすべて』（IPUSIRON）を読んでいたら、私が知ってる楕円ElGamal暗号と少し違う方式（変種）が紹介されていました。 「なるほど、そういうのもあるのだな」と思ったのですが、よく考えると安全性が損なわれているのではと思って考えたことを書いてみます。 単に、不勉強な私が知らなかっただけで大昔からの既知の事実だと思いますが、探してもあまり見当たらなかったのでまとめておきます。 楕円ElGamal暗号 まずは『現代暗号の誕生と発展』（岡本龍明）でも紹介されている、私が知っていた方式を、記号を変えて紹介します。用語は楕円ElGamal暗号も参照してください。 記号の定義 0 以上 r 以下の整数の集合を [0, r], そこからランダムに整数 x を選ぶことを x ← [0, r] と書くことにします。 G を楕円曲線の点 P を生成元とする素数位数 r の巡回群 \lan

初めに 多倍長整数の実装, 有限体の実装と解説してきたので次は楕円曲線暗号の高速な実装方法を紹介します。 しばらくは数学の準備で、まずは射影座標を解説します。射影座標は通常の2次元座標 (x, y) と無限遠点 \infty を統一的に扱う座標です。 一覧 楕円曲線暗号のための数学1（射影座標）(これ) 楕円曲線暗号のための数学2（バイナリ法によるスカラー倍算） 楕円曲線暗号のための数学3（ヤコビ座標） 楕円曲線暗号のための数学4（ウィンドウ法） 楕円曲線暗号のための数学5（NAF） 楕円曲線暗号のための数学6（GLV法と自己準同型写像） 楕円曲線暗号のための数学7（マルチスカラー倍算概要） 楕円曲線暗号のための数学8（マルチスカラー倍算のパラメータ最適化） 楕円曲線の定義 Pythonを使った楕円曲線を実装する話は楕円曲線暗号のPythonによる実装その2（楕円曲線とECDSA）でも解説

初めに 公開鍵による暗号化と署名をプログラマ向け(?)に書いてみました。ちまたによくある暗号化と署名の話はインタフェースと実装がごちゃまぜになっていることが分かり、暗号化と署名の理解が進めば幸いです（と思って書いたけど、余計分からんといわれたらすんません）。登場する言語は架空ですが、多分容易に理解できると思います。 公開鍵による暗号化PKE 早速、公開鍵による暗号化(PKE : Public Key Encryption)を紹介します。登場するのは暗号化したいデータのクラスPlainText, 暗号文クラスCipherText, 秘密鍵クラスPrivateKeyと公開鍵クラスPublicKeyです。PKEは次の3個のインタフェースを提供しています。 abstract class PKE { abstract keyGenerator(): [PrivateKey, PublicKey];

初めに 公開鍵暗号の一種であるElGamal暗号、特に楕円ElGamal暗号を紹介します。 巡回群 まず用語の説明から始めましょう。G を演算を乗法表記で表す群とします（群の説明は群と楕円曲線とECDH鍵共有参照）。 つまり単位元1があり、掛け算が定義されています。G の要素 g を1個とり、1に g を繰り返し掛けます。g^0=1, g^1=g, g^2,g^3 \dots . このようにして作った集合 \langle g \rangle:=\Set{1,g,g^2,g^3,\dots} が G に一致するとき、G を巡回群、g を G の生成元といいます。 特に G が有限群（有限集合の群）であるとき、整数 r に対する g^r はどこかで1に戻らないといけません。戻らないと \langle g \rangle が無限集合になってしまうからです。 g^r=1 となる0でない最小の r

初めに ここでは暗号でよく使われる数学的な概念である群を紹介します。 そして楕円曲線暗号のPythonによる実装その1（有限体とECDH鍵共有）で紹介したECDH鍵共有を群の言葉を使って見直します。 掛け算の重要な性質 群(group)とは日常的に使われる掛け算を抽象化した数学用語です。掛け算は 2 \times 3=6, 4 \times 5 = 20 といったものです。 掛け算は次の性質を持っています。 3個以上の数字を掛けるとき、掛ける順序を変えても変わらない。例 : (2 \times 3) \times 4 = 6 \times 4 = 24. 2 \times (3\times4) = 2\times 12 = 24. 数字に1を掛けても値は変わらない。例 : 123 \times 1 = 123. 逆数を掛けると1になる。例 : 5 \times (1/5) = 1. 1番目

初めに ここではIntel CPUのレイテンシとスループットの基本を解説し、FMAの処理時間を調べます。 レイテンシとスループット レイテンシ CPUにおけるレイテンシ(latency)とは命令が発行されてからその実行が完了するまでの時間（クロックサイクル）です。 たとえばレイテンシが4なら実行されてから4クロックサイクル（以降clkと記す）後にその結果を利用できます。 スループット Intelのマニュアルによるとスループットとは同じ命令を続けて発行するときに待つclkです。たとえばスループットが1なら1clkごとに1命令、0.5なら1clkごとに2命令同時に発行できます。 ただし、通常スループットというと単位時間あたりに処理できる量を表し、大きいほど高性能です（Gbpsなど）。それに従うなら1clkあたりに同じ命令を何個発行できるかという定義になるべきであり、Intelのスループットは逆

初めに 今回はPythonで作ったLLVM DSLを実装します。 記事全体の一覧は有限体の実装一覧参照。 LLVM DSL 多倍長整数の実装8（LLVMを用いたasmコード生成）ではC++によるLLVMコード生成の方法を紹介しました。 あれから同じ機能を持ったPythonによるLLVMコード生成DSLを作ったのでそれを紹介します。 s_xbyak_llvm.pyはDSLからLLVM IRコード（以下ll）を生成するためのPythonツールです。 もともとは、C++でJITを実現するためのXbyakを開発していたのですが、JITじゃなくてもDSLでアセンブラを掛けるのが便利であることが分かってx64用のs_xbyak.pyを開発し（sは静的の意味）、それを今度はLLVMに適用したのです。 PythonによるDSLはコンパイル不要なので楽です。 詳しい説明は先月末に開催されたOpen Sour

初めに 「署名とはメッセージのハッシュ値を秘密鍵で暗号化したものであり、検証は署名を公開鍵で復号してハッシュ値と等しいかを確認することである」という説明(×)をよく見かけます。 正しい署名の定義と実際のRSA署名がどのようなものであり、上記説明(×)がなぜよくないのかを理解しましょう。 署名の定義 署名の解説は署名の概要でも解説しましたが、再掲します。 署名（方式）は鍵生成（KeyGen）、署名（Sign）、検証（Verify）の3個のアルゴリズムからなります。 KeyGenではアリスが署名鍵sと検証鍵Sを生成します。署名鍵sは自分だけの秘密の値なので秘密鍵、検証鍵Sは他人に渡して使ってもらう鍵なので公開鍵ともいいます。 Signは署名したいデータmに対して署名鍵sを使って署名と呼ばれるデータσを作ります。 データmと署名σのペアを他人（ボブ）に渡します。 Verifyはボブが検証鍵Sを使

初めに 前々回多倍長整数の実装1（C/C++）、前回多倍長整数の実装2（Xbyak）でC++やXbyakによる実装をしました。 今回からXbyakに頼らずに、いくつかの方法を試します。まずはコンパイラのintrinsic関数を使ってみましょう。 記事全体の一覧は多倍長整数の実装1（C/C++）参照。 _addcarry_u64 _addcarry_u64はx64命令のadcに相当するコンパイラの組み込み関数です。 利用するにはWindowsならintrin.h, Linuxならx86intrin.hをインクルードします。

お断り この記事は『Software Design2022年3月号』の「第4章：電子署名のプロセスを体験 Pythonによる楕円曲線暗号の実装」の入稿記事を技術評論社のご好意で公開したものです。 元はLaTeXだったのをマークダウンに修正し、二つに分けています。 前半は楕円曲線暗号のPythonによる実装その1（有限体とECDH鍵共有）です。 記事中のサンプルコードはサポートページからダウンロードできます。 楕円曲線クラス 楕円曲線の点 有限体クラスを実装できたので次は楕円曲線クラス\texttt{Ec}を実装します。 楕円曲線は有限体\texttt{Fp}とその値aとbで決まります。 楕円曲線クラスは楕円曲線の節で紹介したようにr個の点0, P, 2P, ....からなる集合です。 secp256k1はTLSやビットコインで使われる楕円曲線のパラメータで、 a=0 b=7 p=2^{25

お断り この記事は『Software Design2022年3月号』の「第4章：電子署名のプロセスを体験 Pythonによる楕円曲線暗号の実装」の入稿記事を技術評論社のご好意で公開したものです。 元はLaTeXだったのをマークダウンに修正し、二つに分けています。 記事中のサンプルコードはサポートページからダウンロードできます。 はじめに この章では楕円曲線を用いた鍵共有や署名をPythonで実装します。実装するために必要な数学は随時解説します。 動作確認はPython 3.8.10で行いました。 コードは動作原理を理解するためのものであり、細かいエラー処理などはしていません。 プロダクト製品などで利用できるものではないことをご了承ください。 用語のおさらい 楕円曲線暗号の位置づけ まず最初に用語の確認をします。 「暗号」は複数の意味で使われます。 一つは「データを秘匿化するために、他人に読

イラストで正しく理解するTLS 1.3の暗号技術 初めに ここではTLS 1.3（以下TLSと略記）で使われている暗号技術を解説します。 主眼はTLSのプロトコルではなく、「暗号技術」の用語の挙動（何を入力して何を出力するのか）と目的の理解です。 実際にどのような方式なのかといった、より詳しい説明は拙著『図解即戦力 暗号と認証のしくみと理論がこれ1冊でしっかりわかる教科書』（暗認本）や『暗認本』の内容を紹介したスライドや動画などの資料集をごらんください。 なお表題の「イラストで」は数式を使わないという程度の意味です。 TLSで守りたいもの TLSはコンピュータ同士が安全に通信するための規格です。 主に人がブラウザを介して「https://」で始まるWebサイトにアクセスするときに利用されます。 安全に通信するためには、通信内容が盗聴されても情報が漏れない機密性が必要です。 それから通信が改