Clever Geek Handbook

PythonのCIS諸国のEDS

画像

こんにちは

CIS諸国のブロック暗号の実装については、すでにHabréで書いています。 ロシアのGOST 34.10-2012、ウクライナのDSTU 4145-2002、およびベラルーシのSTB 34.101.45-2013の対称標準にデジタル署名アルゴリズムが追加された結果、別の無料の週が発行されました。

3つのアルゴリズムはすべて楕円曲線に基づいています 。 しかし、各標準の実装には独自の微妙さがあり、この記事で簡単に説明します。





GOST 34.10-2012



したがって、私たちはロシアの標準から始めます。 ここではすべてが非常に単純であり、必要なものはすべて標準のテキストで詳しく説明されており、例が示されています。 このアルゴリズムは、大きな素数pの体上の楕円曲線（EC）の点群で機能します。 有限な単純体上のECは、ワイエルシュトラス方程式で記述される点の集合であることを思い出すことは不要ではありません。



したがって、アルゴリズムを使用する場合、最初にECパラメーターを決定する必要があります。つまり、大きな素数qと等しい次数で、数a、b、nおよび基点Pを選択する必要があります。 つまり、ポイントにqより小さい数値を掛けると、毎回完全に異なるポイントが取得されます。

パラメータを選択したら、秘密と公開鍵のペアの生成に進むことができます。

秘密鍵dは、不等式0 <d <qを満たすランダムな大きな数です。

公開鍵-Q = d * Pとして計算される楕円曲線Qの点



デジタル署名を作成するプロセスは、次のアルゴリズムに従って実行されます。

  1. メッセージハッシュMを計算します。H= h（M）;
  2. バイナリ表現がHである整数αを計算します。
  3. e =αmod qを決定します。e= 0の場合、e = 1に設定します。
  4. 条件0 <k <qを満たす乱数kを生成します。
  5. 楕円曲線の点C = k * Pを計算します。
  6. r = x C mod qを決定します。ここで、x Cは点Cのx座標です。r= 0の場合、手順4に戻ります。
  7. 値s =（rd + ke）mod qを計算します。 s = 0の場合、ステップ4に戻ります。
  8. r || sの値をデジタル署名として返します。


署名を検証するには、次の手順を実行する必要があります。

  1. 受信した署名を使用して、番号rとsを復元します。 不等式0 <r <qおよび0 <s <qが満たされない場合、「署名が正しくありません」を返します。
  2. メッセージハッシュMを計算します。H= h（M）;
  3. バイナリ表現がHである整数αを計算します。
  4. e =αmod qを決定します。e= 0の場合、e = 1に設定します。
  5. v = e -1 mod qを計算します。
  6. 値z1 = s * v mod qおよびz2 = -r * v mod qを計算します。
  7. 楕円曲線の点C = z1 * G + z2 * Qを計算します。
  8. R = x c mod qを決定します。ここで、x cは点Cのx座標です。
  9. R = rの場合、署名は正しいです。 それ以外の場合、署名は受け入れられません。


アルゴリズムをテストするには、標準のテキストの例を使用できます。

GOSTの使用例： 
def test_gost_sign(): p = 57896044618658097711785492504343953926634992332820282019728792003956564821041 a = 7 b = 43308876546767276905765904595650931995942111794451039583252968842033849580414 x = 2 y = 4018974056539037503335449422937059775635739389905545080690979365213431566280 q = 57896044618658097711785492504343953927082934583725450622380973592137631069619 gost = DSGOST(p, a, b, q, x, y) key = 55441196065363246126355624130324183196576709222340016572108097750006097525544 message = 20798893674476452017134061561508270130637142515379653289952617252661468872421 k = 53854137677348463731403841147996619241504003434302020712960838528893196233395 sign = gost.sign(message, key, k) def test_gost_verify(): p = 57896044618658097711785492504343953926634992332820282019728792003956564821041 a = 7 b = 43308876546767276905765904595650931995942111794451039583252968842033849580414 x = 2 y = 4018974056539037503335449422937059775635739389905545080690979365213431566280 q = 57896044618658097711785492504343953927082934583725450622380973592137631069619 gost = DSGOST(p, a, b, q, x, y) message = 20798893674476452017134061561508270130637142515379653289952617252661468872421 sign = (29700980915817952874371204983938256990422752107994319651632687982059210933395, 574973400270084654178925310019147038455227042649098563933718999175515839552) q_x = 57520216126176808443631405023338071176630104906313632182896741342206604859403 q_y = 17614944419213781543809391949654080031942662045363639260709847859438286763994 public_key = ECPoint(q_x, q_y, a, b, p) is_signed = gost.verify(message, sign, public_key)




すべての結果が所定の例と一致することを確認し、次の標準に進みます。



STB 34.101.45-2013



ベラルーシの標準はGOSTに非常に似ています。 楕円曲線と基点は、パラメーターa、b、n、P、およびqによって決まります。

秘密鍵はdです。 公開キーはポイントQ = d * Pです。



署名を生成するには、次の手順を実行します。

  1. H←Set（H）を設定します。
  2. k←{1、2、...、q-1}を解きます。
  3. R←kPを設定します。
  4. S 0を設定←|ベルトハッシュ（OID（ℎ）‖| R | 2l‖H ）| l
  5. S 1を設定←|（k-H-（S 0 + 2 l ）d）mod q | 2l
  6. S←S 0‖S 1を設定します。
  7. Sを返します


署名検証手順は次のようになります。

  1. SをS = S 0‖S 1の形式で表します。ここで、S 0∈{0、1} l 、S 1∈ {0、1} 2lです。
  2. S 1 > qの場合、NOを返します。
  3. H←Set（X）を設定します。
  4. R←（︀（S 1 + H）mod q）︀P +（S 0 + 2 l ）Qを設定します。
  5. R = Oの場合、NOを返します。
  6. t←|ベルトハッシュ（OID（ℎ）‖| R | 2l‖H ）| l
  7. S 0 ！= Tの場合、NOを返します。
  8. YESを返します。


ここで、 lはビット抵抗レベルです（楕円曲線上の回路の場合、このインジケーターはキーの長さの半分にほぼ等しくなります）。

Hはハッシュ関数です。

OIDは、使用されるハッシュアルゴリズムの識別子です。 ベルトハッシュを使用する場合、この値は常に0x 06092A7000020022651F51です。

| R | l-数Rの最初のlビット

|| -2つのビットシーケンスの連結。

ご覧のように、標準ではハッシュ関数のベルトハッシュの使用が厳密に記述されています。これがないと、実装されたアルゴリズムの正確性を検証することはできません。

幸いなことに、この関数は、ベラルーシ共和国のベルトブロック暗号化標準に基づいています。Pythonでの実装については、 こちらをご覧ください 。 ハッシュアルゴリズムが完了すると、デジタル署名自体の実装を開始できます。 ただし、これには、標準STB 34.101.45-2013の別の機能を考慮する必要があります。 例の数値はすべてリトルエンディアン表記で示されており、結果が標準で指定されている数値と一致するようにするには、それらをビッグエンディアンに変換する必要があります。

標準の例を確認することにより 
 def test_stb_sign(): p = 0x43FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF p = reverse(p) a = 0x40FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF a = reverse(a) b = 0xF1039CD66B7D2EB253928B976950F54CBEFBD8E4AB3AC1D2EDA8F315156CCE77 b = reverse(b) q = 0x07663D2699BF5A7EFC4DFB0DD68E5CD9FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF q = reverse(q) y = 0x936A510418CF291E52F608C4663991785D83D651A3C9E45C9FD616FB3CFCF76B y = reverse(y) d = 0x1F66B5B84B7339674533F0329C74F21834281FED0732429E0C79235FC273E269 d = reverse(d) stb = STB(p, a, b, q, y, 128) message = 0xB194BAC80A08F53B366D008E58 k = 0x4C0E74B2CD5811AD21F23DE7E0FA742C3ED6EC483C461CE15C33A77AA308B7D2 k = reverse(k) signature = stb.sign(message, d, k) def test_stb_verify(): p = 0x43FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF p = reverse(p) a = 0x40FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF a = reverse(a) b = 0xF1039CD66B7D2EB253928B976950F54CBEFBD8E4AB3AC1D2EDA8F315156CCE77 b = reverse(b) q = 0x07663D2699BF5A7EFC4DFB0DD68E5CD9FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF q = reverse(q) y = 0x936A510418CF291E52F608C4663991785D83D651A3C9E45C9FD616FB3CFCF76B y = reverse(y) message = 0xB194BAC80A08F53B366D008E584A5DE48504FA9D1BB6C7AC252E72C202FDCE0D5BE3D61217B96181FE6786AD716B890B q_x = 0xBD1A5650179D79E03FCEE49D4C2BD5DDF54CE46D0CF11E4FF87BF7A890857FD0 q_x = reverse(q_x) q_y = 0x7AC6A60361E8C8173491686D461B2826190C2EDA5909054A9AB84D2AB9D99A90 q_y = reverse(q_y) s = (0x47A63C8B9C936E94B5FAB3D9CBD78366, 0x290F3210E163EEC8DB4E921E8479D4138F112CC23E6DCE65EC5FF21DF4231C28) pub_key = (q_x, q_y) stb = STB(p, a, b, q, y, 128) is_signed = stb.verify(message, pub_key, s)




DSTU 4145-2002に渡します。



DSTU 4145-2002



以前の2つの標準とは異なり、DSTU 4145-2002は特性2のフィールド上の楕円曲線に基づいています。つまり、まったく異なる数学が機能します。 主な違いは、算術演算が数値ではなく多項式で実行されることです。 この標準では、数学演算の実装に、多項式ベースと最適な通常ベースの2つのオプションが用意されています。 最初のオプションを実装しました。

アルゴリズムは、次のパラメーターによって設定されます。

A、B -ECの方程式の係数 画像

k、mはメンバーの数と、すべての算術演算が実行されるモジュロである主多項式の最高次数です。 たとえば、k = 5、m = 5は次の多項式を定義します： x ^ 5 + x ^ 3 + x ^ 2 + x + 1 。

P-次数nのベースポイント。

キーペアは、プライベートキーdとパブリックキーQ = -d * Pで構成されます。



署名生成手順は次のとおりです。

  1. 1 <e <nとなるような数eを生成します。
  2. ポイントR = e * Pを計算します。
  3. 多項式f_r = R_x * h（M）を計算します。ここで、R_xは点Rのx座標です。 h（M）は、署名されたメッセージMのハッシュです。

  4. f_rを数値rとして表します。

  5. 数s =（e + d * r）mod nを計算します。
  6. ペアとして（r、s）を返します。




署名を検証するには：

  1. 署名は数字のペア（r、s）で表されます。

  2. ECポイントR = s * P + r * Qを計算します。
  3. メインフィールドf_r = h（M）* R_xの要素を計算します。
  4. f_rを数値r1として表します。
  5. 等式r1 = rが成り立つ場合、署名は正しい


テストケースを実行する 
 def test_dstu_sign(): dstu_x = 0x72D867F93A93AC27DF9FF01AFFE74885C8C540420 dstu_y = 0x0224A9C3947852B97C5599D5F4AB81122ADC3FD9B dstu_a = 0x1 dstu_b = 0x5FF6108462A2DC8210AB403925E638A19C1455D21 dstu_p = 0x800000000000000000000000000000000000000c9 dstu_n = 0x400000000000000000002BEC12BE2262D39BCF14D dstu = DSTU4145(dstu_p, dstu_a, dstu_b, dstu_x, dstu_y, dstu_n) message = 0x03A2EB95B7180166DDF73532EEB76EDAEF52247FF dstu_d = 0x183F60FDF7951FF47D67193F8D073790C1C9B5A3E dstu_e = 0x1025E40BD97DB012B7A1D79DE8E12932D247F61C6 signature = dstu.sign(message, dstu_d, dstu_e) def test_dstu_verify(): dstu_x = 0x72D867F93A93AC27DF9FF01AFFE74885C8C540420 dstu_y = 0x0224A9C3947852B97C5599D5F4AB81122ADC3FD9B dstu_a = 0x1 dstu_b = 0x5FF6108462A2DC8210AB403925E638A19C1455D21 dstu_p = 0x800000000000000000000000000000000000000c9 dstu_n = 0x400000000000000000002BEC12BE2262D39BCF14D dstu = DSTU4145(dstu_p, dstu_a, dstu_b, dstu_x, dstu_y, dstu_n) message = 0x03A2EB95B7180166DDF73532EEB76EDAEF52247FF dstu_d = 0x183F60FDF7951FF47D67193F8D073790C1C9B5A3E dstu_Q = dstu.gen_keys(dstu_d)[1] signature = (0x274EA2C0CAA014A0D80A424F59ADE7A93068D08A7, 0x2100D86957331832B8E8C230F5BD6A332B3615ACA) is_signed = dstu.verify(message, signature, dstu_Q)




期待される結果を取得します。



PS



そうそう、ソース。 GitHubで上記のすべてのアルゴリズムのPythonのソースコードを見つけることができます。



参照資料



  1. 標準GOST 34.10-2012のテキスト。
  2. 標準のSTB 34.101.45-2013のテキスト。
  3. 標準DSTU 4145-2002のテキスト（ウクライナ語では、ECポイントの追加を説明する式にエラーが含まれています）。


More articles:


All Articles