[要約] RFC 8554は、Leighton-Micali署名（LMS）と呼ばれるハッシュベースの署名スキームについて説明しています。この文書は、量子コンピュータによる攻撃に対して耐性を持つことを目的とした、公開鍵署名アルゴリズムの仕様を提供します。LMS署名は、特に長期間のセキュリティが必要なデジタル署名、ソフトウェアの署名、または量子コンピュータの脅威に対処する必要がある場面での利用が想定されています。関連するRFCとしては、RFC 8391（XMSS: eXtended Merkle Signature Scheme）があり、これもハッシュベースの署名スキームに関するもので、量子コンピュータに対する耐性を提供します。
Internet Research Task Force (IRTF) D. McGrew
Request for Comments: 8554 M. Curcio
Category: Informational S. Fluhrer
ISSN: 2070-1721 Cisco Systems
April 2019
Leighton-Micali Hash-Based Signatures
Leighton-Micaliハッシュベースの署名
Abstract
概要
This note describes a digital-signature system based on cryptographic hash functions, following the seminal work in this area of Lamport, Diffie, Winternitz, and Merkle, as adapted by Leighton and Micali in 1995. It specifies a one-time signature scheme and a general signature scheme. These systems provide asymmetric authentication without using large integer mathematics and can achieve a high security level. They are suitable for compact implementations, are relatively simple to implement, and are naturally resistant to side-channel attacks. Unlike many other signature systems, hash-based signatures would still be secure even if it proves feasible for an attacker to build a quantum computer.
このノートは、1995年にレイトンとミカリによって採用された、ランポート、ディフィー、ヴィンターニッツ、およびマークルのこの領域における独創的な研究に続く、暗号ハッシュ関数に基づくデジタル署名システムについて説明します。ワンタイム署名スキームと一般的な署名スキーム。これらのシステムは、大きな整数の数学を使用せずに非対称認証を提供し、高いセキュリティレベルを実現できます。これらはコンパクトな実装に適しており、実装が比較的簡単で、サイドチャネル攻撃に対する耐性があります。他の多くの署名システムとは異なり、ハッシュベースの署名は、攻撃者が量子コンピュータを構築することが可能であると証明されたとしても、安全です。
This document is a product of the Crypto Forum Research Group (CFRG) in the IRTF. This has been reviewed by many researchers, both in the research group and outside of it. The Acknowledgements section lists many of them.
この文書は、IRTFの暗号フォーラム研究グループ（CFRG）の製品です。これは、研究グループ内外の多くの研究者によってレビューされています。謝辞セクションにはそれらの多くがリストされています。
Status of This Memo
本文書の状態
This document is not an Internet Standards Track specification; it is published for informational purposes.
このドキュメントはInternet Standards Trackの仕様ではありません。情報提供を目的として公開されています。
This document is a product of the Internet Research Task Force (IRTF). The IRTF publishes the results of Internet-related research and development activities. These results might not be suitable for deployment. This RFC represents the consensus of the Crypto Forum Research Group of the Internet Research Task Force (IRTF). Documents approved for publication by the IRSG are not candidates for any level of Internet Standard; see Section 2 of RFC 7841.
この文書は、Internet Research Task Force（IRTF）の製品です。 IRTFは、インターネット関連の研究開発活動の結果を公開しています。これらの結果は、展開に適さない可能性があります。このRFCは、インターネット研究タスクフォース（IRTF）の暗号フォーラム研究グループの合意を表します。 IRSGによる公開が承認されたドキュメントは、どのレベルのインターネット標準の候補にもなりません。 RFC 7841のセクション2をご覧ください。
Information about the current status of this document, any errata, and how to provide feedback on it may be obtained at https://www.rfc-editor.org/info/rfc8554.
このドキュメントの現在のステータス、エラッタ、およびフィードバックの提供方法に関する情報は、https：//www.rfc-editor.org/info/rfc8554で入手できます。
Copyright Notice
著作権表示
Copyright (c) 2019 IETF Trust and the persons identified as the document authors. All rights reserved.
Copyright（c）2019 IETF Trustおよびドキュメントの作成者として識別された人物。全著作権所有。
This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document.
この文書は、BCP 78およびIETF文書に関するIETFトラストの法的規定（https://trustee.ietf.org/license-info）の対象であり、この文書の発行日に有効です。これらのドキュメントは、このドキュメントに関するあなたの権利と制限を説明しているため、注意深く確認してください。
Table of Contents
目次
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1. CFRG Note on Post-Quantum Cryptography . . . . . . . . . 5
1.2. Intellectual Property . . . . . . . . . . . . . . . . . . 6
1.2.1. Disclaimer . . . . . . . . . . . . . . . . . . . . . 6
1.3. Conventions Used in This Document . . . . . . . . . . . . 6
2. Interface . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3. Notation . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . 7
3.1.1. Operators . . . . . . . . . . . . . . . . . . . . . . 7
3.1.2. Functions . . . . . . . . . . . . . . . . . . . . . . 8
3.1.3. Strings of w-Bit Elements . . . . . . . . . . . . . . 8
3.2. Typecodes . . . . . . . . . . . . . . . . . . . . . . . . 9
3.3. Notation and Formats . . . . . . . . . . . . . . . . . . 9
4. LM-OTS One-Time Signatures . . . . . . . . . . . . . . . . . 12
4.1. Parameters . . . . . . . . . . . . . . . . . . . . . . . 13
4.2. Private Key . . . . . . . . . . . . . . . . . . . . . . . 14
4.3. Public Key . . . . . . . . . . . . . . . . . . . . . . . 15
4.4. Checksum . . . . . . . . . . . . . . . . . . . . . . . . 15
4.5. Signature Generation . . . . . . . . . . . . . . . . . . 16
4.6. Signature Verification . . . . . . . . . . . . . . . . . 17
5. Leighton-Micali Signatures . . . . . . . . . . . . . . . . . 19
5.1. Parameters . . . . . . . . . . . . . . . . . . . . . . . 19
5.2. LMS Private Key . . . . . . . . . . . . . . . . . . . . . 20
5.3. LMS Public Key . . . . . . . . . . . . . . . . . . . . . 21
5.4. LMS Signature . . . . . . . . . . . . . . . . . . . . . . 22
5.4.1. LMS Signature Generation . . . . . . . . . . . . . . 23
5.4.2. LMS Signature Verification . . . . . . . . . . . . . 24
6. Hierarchical Signatures . . . . . . . . . . . . . . . . . . . 26
6.1. Key Generation . . . . . . . . . . . . . . . . . . . . . 29
6.2. Signature Generation . . . . . . . . . . . . . . . . . . 30
6.3. Signature Verification . . . . . . . . . . . . . . . . . 32
6.4. Parameter Set Recommendations . . . . . . . . . . . . . . 32
7. Rationale . . . . . . . . . . . . . . . . . . . . . . . . . . 34
7.1. Security String . . . . . . . . . . . . . . . . . . . . . 35
8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 36
9. Security Considerations . . . . . . . . . . . . . . . . . . . 38
9.1. Hash Formats . . . . . . . . . . . . . . . . . . . . . . 39
9.2. Stateful Signature Algorithm . . . . . . . . . . . . . . 40
9.3. Security of LM-OTS Checksum . . . . . . . . . . . . . . . 41
10. Comparison with Other Work . . . . . . . . . . . . . . . . . 42
11. References . . . . . . . . . . . . . . . . . . . . . . . . . 43
11.1. Normative References . . . . . . . . . . . . . . . . . . 43
11.2. Informative References . . . . . . . . . . . . . . . . . 43
Appendix A. Pseudorandom Key Generation . . . . . . . . . . . . 45
Appendix B. LM-OTS Parameter Options . . . . . . . . . . . . . . 45
Appendix C. An Iterative Algorithm for Computing an LMS Public
Key . . . . . . . . . . . . . . . . . . . . . . . . 47
Appendix D. Method for Deriving Authentication Path for a
Signature . . . . . . . . . . . . . . . . . . . . . 48
Appendix E. Example Implementation . . . . . . . . . . . . . . . 49
Appendix F. Test Cases . . . . . . . . . . . . . . . . . . . . . 49
Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . 60
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 61
One-time signature systems, and general-purpose signature systems built out of one-time signature systems, have been known since 1979 [Merkle79], were well studied in the 1990s [USPTO5432852], and have benefited from renewed attention in the last decade. The characteristics of these signature systems are small private and public keys and fast signature generation and verification, but large signatures and moderately slow key generation (in comparison with RSA and ECDSA (Elliptic Curve Digital Signature Algorithm)). Private keys can be made very small by appropriate key generation, for example, as described in Appendix A. In recent years, there has been interest in these systems because of their post-quantum security and their suitability for compact verifier implementations.
ワンタイム署名システム、およびワンタイム署名システムから構築された汎用署名システムは、1979年から知られており[Merkle79]、1990年代によく研究されており[USPTO5432852]、過去10年間に新たな注目が集まっています。 。これらの署名システムの特徴は、小さな秘密鍵と公開鍵、高速な署名生成と検証ですが、大きな署名と適度に遅い鍵生成です（RSAおよびECDSA（楕円曲線デジタル署名アルゴリズム）と比較して）。秘密キーは、たとえば付録Aで説明されているように、適切なキー生成によって非常に小さくすることができます。近年、これらのシステムは、量子化後のセキュリティとコンパクトな検証機能の実装に適しているため、関心が寄せられています。
This note describes the Leighton and Micali adaptation [USPTO5432852] of the original Lamport-Diffie-Winternitz-Merkle one-time signature system [Merkle79] [C:Merkle87] [C:Merkle89a] [C:Merkle89b] and general signature system [Merkle79] with enough specificity to ensure interoperability between implementations.
このメモは、元のランポート-ディフィー-ウィンターニッツ-メルクルのワンタイム署名システム[Merkle79] [C：Merkle87] [C：Merkle89a] [C：Merkle89b]および一般的な署名システム[Merkle79]のレイトンおよびミカリ適応[USPTO5432852]について説明します。 ]実装間の相互運用性を保証するのに十分な特異性を備えています。
A signature system provides asymmetric message authentication. The key-generation algorithm produces a public/private key pair. A message is signed by a private key, producing a signature, and a message/signature pair can be verified by a public key. A One-Time Signature (OTS) system can be used to sign one message securely but will become insecure if more than one is signed with the same public/ private key pair. An N-time signature system can be used to sign N or fewer messages securely. A Merkle-tree signature scheme is an N-time signature system that uses an OTS system as a component.
署名システムは、非対称メッセージ認証を提供します。鍵生成アルゴリズムは、公開/秘密鍵のペアを生成します。メッセージは秘密鍵で署名され、署名を生成します。メッセージ/署名のペアは公開鍵で検証できます。ワンタイム署名（OTS）システムは、1つのメッセージに安全に署名するために使用できますが、複数のものが同じ公開/秘密鍵のペアで署名されている場合、安全ではなくなります。 N回署名システムを使用すると、N以下のメッセージに安全に署名できます。マークルツリー署名方式は、OTSシステムをコンポーネントとして使用するN回署名システムです。
In the Merkle scheme, a binary tree of height h is used to hold 2^h OTS key pairs. Each interior node of the tree holds a value that is the hash of the values of its two child nodes. The public key of the tree is the value of the root node (a recursive hash of the OTS public keys), while the private key of the tree is the collection of all the OTS private keys, together with the index of the next OTS private key to sign the next message with.
マークルスキームでは、高さhのバイナリツリーが2 ^ h OTSキーペアを保持するために使用されます。ツリーの各内部ノードは、2つの子ノードの値のハッシュである値を保持します。ツリーの公開鍵はルートノードの値（OTS公開鍵の再帰ハッシュ）ですが、ツリーの秘密鍵は、次のOTS秘密鍵のインデックスを含むすべてのOTS秘密鍵のコレクションです。次のメッセージに署名するためのキー。
In this note, we describe the Leighton-Micali Signature (LMS) system (a variant of the Merkle scheme) with the Hierarchical Signature System (HSS) built on top of it that allows it to efficiently scale to larger numbers of signatures. In order to support signing a large number of messages on resource-constrained systems, the Merkle tree can be subdivided into a number of smaller trees. Only the bottommost tree is used to sign messages, while trees above that are used to sign the public keys of their children. For example, in the simplest case with two levels with both levels consisting of height h trees, the root tree is used to sign 2^h trees with 2^h OTS key pairs, and each second-level tree has 2^h OTS key pairs, for a total of 2^(2h) bottom-level key pairs, and so can sign 2^(2h) messages. The advantage of this scheme is that only the active trees need to be instantiated, which saves both time (for key generation) and space (for key storage). On the other hand, using a multilevel signature scheme increases the size of the signature as well as the signature verification time.
このノートでは、Leighton-Micali Signature（LMS）システム（Merkleスキームのバリアント）と、その上に構築されたHierarchical Signature System（HSS）を使用して、より多くの署名に効率的にスケーリングできるようにします。リソースに制約のあるシステムで多数のメッセージへの署名をサポートするために、マークルツリーをいくつかの小さなツリーに分割できます。一番下のツリーだけがメッセージの署名に使用され、その上のツリーはその子の公開鍵の署名に使用されます。たとえば、両方のレベルが高さhのツリーで構成される2つのレベルの最も単純なケースでは、ルートツリーは2 ^ hのツリーに2 ^ hのOTSキーペアで署名するために使用され、各第2レベルのツリーには2 ^ hのOTSキーがありますペア、合計2 ^（2h）の最下位レベルのキーペア、つまり2 ^（2h）メッセージに署名できます。このスキームの利点は、インスタンス化する必要があるのはアクティブなツリーのみであるため、時間（キー生成）とスペース（キーストレージ）の両方を節約できることです。一方、マルチレベル署名方式を使用すると、署名のサイズと署名の検証時間が長くなります。
This note is structured as follows. Notes on post-quantum cryptography are discussed in Section 1.1. Intellectual property issues are discussed in Section 1.2. The notation used within this note is defined in Section 3, and the public formats are described in Section 3.3. The Leighton-Micali One-Time Signature (LM-OTS) system is described in Section 4, and the LMS and HSS N-time signature systems are described in Sections 5 and 6, respectively. Sufficient detail is provided to ensure interoperability. The rationale for the design decisions is given in Section 7. The IANA registry for these signature systems is described in Section 8. Security considerations are presented in Section 9. Comparison with another hash-based signature algorithm (eXtended Merkle Signature Scheme (XMSS)) is in Section 10.
このノートは次のように構成されています。量子化後の暗号化に関する注意事項は、セクション1.1で説明します。知的財産の問題については、セクション1.2で説明します。この注記で使用されている表記法はセクション3で定義されており、公開形式はセクション3.3で説明されています。 Leighton-Micaliワンタイム署名（LM-OTS）システムについてはセクション4で説明し、LMSおよびHSS Nタイム署名システムについてはそれぞれセクション5および6で説明します。相互運用性を確保するために十分な詳細が提供されます。設計決定の根拠はセクション7に記載されています。これらの署名システムのIANAレジストリについてはセクション8で説明されています。セキュリティに関する考慮事項はセクション9で説明されています。別のハッシュベースの署名アルゴリズム（拡張マークル署名スキーム（XMSS））との比較セクション10にあります。
This document represents the rough consensus of the CFRG.
このドキュメントは、CFRGの大まかなコンセンサスを表しています。
All post-quantum algorithms documented by the Crypto Forum Research Group (CFRG) are today considered ready for experimentation and further engineering development (e.g., to establish the impact of performance and sizes on IETF protocols). However, at the time of writing, we do not have significant deployment experience with such algorithms.
Crypto Forum Research Group（CFRG）によって文書化されたすべてのポスト量子アルゴリズムは、今日、実験およびさらなるエンジニアリング開発の準備ができていると見なされています（たとえば、IETFプロトコルに対するパフォーマンスとサイズの影響を確立するため）。ただし、執筆時点では、そのようなアルゴリズムを使用した展開に関する重要な経験はありません。
Many of these algorithms come with specific restrictions, e.g., change of classical interface or less cryptanalysis of proposed parameters than established schemes. The CFRG has consensus that all documents describing post-quantum technologies include the above paragraph and a clear additional warning about any specific restrictions, especially as those might affect use or deployment of the specific scheme. That guidance may be changed over time via document updates.
これらのアルゴリズムの多くには、従来のインターフェースの変更や、確立されたスキームよりも提案されたパラメーターの解読性の低下など、特定の制限が伴います。 CFRGは、量子化後のテクノロジーを説明するすべてのドキュメントに上記の段落と、特に特定のスキームの使用または展開に影響を与える可能性がある特定の制限に関する明確な追加警告が含まれていることに合意しています。このガイダンスは、ドキュメントの更新により、時間の経過とともに変更される可能性があります。
Additionally, for LMS:
さらに、LMSの場合：
CFRG consensus is that we are confident in the cryptographic security of the signature schemes described in this document against quantum computers, given the current state of the research community's knowledge about quantum algorithms. Indeed, we are confident that the security of a significant part of the Internet could be made dependent on the signature schemes defined in this document, if developers take care of the following.
CFRGのコンセンサスは、量子アルゴリズムに対する研究コミュニティの知識の現状を考えると、量子コンピュータに対するこのドキュメントで説明されている署名方式の暗号セキュリティに自信があるということです。実際、インターネットの重要な部分のセキュリティは、開発者が次のことに注意を払えば、このドキュメントで定義されている署名方式に依存する可能性があると確信しています。
In contrast to traditional signature schemes, the signature schemes described in this document are stateful, meaning the secret key changes over time. If a secret key state is used twice, no cryptographic security guarantees remain. In consequence, it becomes feasible to forge a signature on a new message. This is a new property that most developers will not be familiar with and requires careful handling of secret keys. Developers should not use the schemes described here except in systems that prevent the reuse of secret key states.
従来の署名方式とは対照的に、このドキュメントで説明する署名方式はステートフルです。つまり、秘密鍵は時間とともに変化します。秘密鍵の状態が2回使用される場合、暗号化によるセキュリティの保証は残りません。その結果、新しいメッセージの署名を偽造することが可能になります。これは、ほとんどの開発者が慣れていない新しいプロパティであり、秘密鍵の慎重な処理が必要です。開発者は、秘密鍵の状態の再利用を防ぐシステムを除いて、ここで説明されているスキームを使用しないでください。
Note that the fact that the schemes described in this document are stateful also implies that classical APIs for digital signatures cannot be used without modification. The API MUST be able to handle a dynamic secret key state; that is, the API MUST allow the signature-generation algorithm to update the secret key state.
このドキュメントで説明されているスキームがステートフルであることは、デジタル署名用の従来のAPIを変更せずに使用できないことも意味していることに注意してください。 APIは動的な秘密鍵の状態を処理できる必要があります。つまり、APIは、署名生成アルゴリズムが秘密鍵の状態を更新することを許可する必要があります。
This document is based on U.S. Patent 5,432,852, which was issued over twenty years ago and is thus expired.
このドキュメントは、20年以上前に発行され、有効期限が切れた米国特許5,432,852に基づいています。
This document is not intended as legal advice. Readers are advised to consult with their own legal advisers if they would like a legal interpretation of their rights.
この文書は法的助言を意図したものではありません。読者は、自分の権利の法的解釈が必要な場合は、自分の法務アドバイザーに相談することをお勧めします。
The IETF policies and processes regarding intellectual property and patents are outlined in [RFC8179] and at <https://datatracker.ietf.org/ipr/about>.
知的財産と特許に関するIETFのポリシーとプロセスは、[RFC8179]と<https://datatracker.ietf.org/ipr/about>で概説されています。
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here.
キーワード「MUST」、「MUST NOT」、「REQUIRED」、「SHALL」、「SHALL NOT」、「SHOULD」、「SHOULD NOT」、「RECOMMENDED」、「NOT RECOMMENDED」、「MAY」、「OPTIONALこのドキュメントの「」は、BCP 14 [RFC2119] [RFC8174]で説明されているように解釈されます。
The LMS signing algorithm is stateful; it modifies and updates the private key as a side effect of generating a signature. Once a particular value of the private key is used to sign one message, it MUST NOT be used to sign another.
LMS署名アルゴリズムはステートフルです。署名を生成する副作用として、秘密鍵を変更および更新します。秘密鍵の特定の値を使用して1つのメッセージに署名した後は、その値を使用して別のメッセージに署名することはできません。
The key-generation algorithm takes as input an indication of the parameters for the signature system. If it is successful, it returns both a private key and a public key. Otherwise, it returns an indication of failure.
鍵生成アルゴリズムは、署名システムのパラメーターの指示を入力として受け取ります。成功すると、秘密鍵と公開鍵の両方が返されます。それ以外の場合は、失敗の表示を返します。
The signing algorithm takes as input the message to be signed and the current value of the private key. If successful, it returns a signature and the next value of the private key, if there is such a value. After the private key of an N-time signature system has signed N messages, the signing algorithm returns the signature and an indication that there is no next value of the private key that can be used for signing. If unsuccessful, it returns an indication of failure.
署名アルゴリズムは、署名されるメッセージと秘密鍵の現在の値を入力として受け取ります。成功すると、署名と秘密鍵の次の値（そのような値がある場合）が返されます。 N回署名システムの秘密鍵がN個のメッセージに署名した後、署名アルゴリズムは署名と、署名に使用できる秘密鍵の次の値がないことを示す標識を返します。失敗した場合は、失敗の表示を返します。
The verification algorithm takes as input the public key, a message, and a signature; it returns an indication of whether or not the signature-and-message pair is valid.
検証アルゴリズムは、公開鍵、メッセージ、および署名を入力として受け取ります。署名とメッセージのペアが有効かどうかを示します。
A message/signature pair is valid if the signature was returned by the signing algorithm upon input of the message and the private key corresponding to the public key; otherwise, the signature and message pair is not valid with probability very close to one.
メッセージと署名のペアは、メッセージと公開鍵に対応する秘密鍵の入力時に署名アルゴリズムによって署名が返された場合に有効です。そうでない場合、署名とメッセージのペアは、1に非常に近い確率で有効ではありません。
Bytes and byte strings are the fundamental data types. A single byte is denoted as a pair of hexadecimal digits with a leading "0x". A byte string is an ordered sequence of zero or more bytes and is denoted as an ordered sequence of hexadecimal characters with a leading "0x". For example, 0xe534f0 is a byte string with a length of three. An array of byte strings is an ordered set, indexed starting at zero, in which all strings have the same length.
バイトとバイト文字列は、基本的なデータ型です。 1バイトは、先頭に「0x」が付いた16進数のペアとして表されます。バイト文字列は、0バイト以上の順序付けられたシーケンスであり、先頭に「0x」が付いた16進文字の順序付けられたシーケンスとして示されます。たとえば、0xe534f0は長さが3のバイト文字列です。バイト文字列の配列は、0から始まるインデックス付きの順序付けされたセットであり、すべての文字列は同じ長さです。
Unsigned integers are converted into byte strings by representing them in network byte order. To make the number of bytes in the representation explicit, we define the functions u8str(X), u16str(X), and u32str(X), which take a nonnegative integer X as input and return one-, two-, and four-byte strings, respectively. We also make use of the function strTou32(S), which takes a four-byte string S as input and returns a nonnegative integer; the identity u32str(strTou32(S)) = S holds for any four-byte string S.
符号なし整数は、ネットワークバイトオーダーで表すことにより、バイト文字列に変換されます。表現のバイト数を明示的にするために、関数u8str（X）、u16str（X）、およびu32str（X）を定義します。これらは非負の整数Xを入力として取り、1、2、および4を返しますそれぞれバイト文字列。また、関数strTou32（S）を使用します。この関数は、4バイトの文字列Sを入力として受け取り、負でない整数を返します。アイデンティティu32str（strTou32（S））= Sは、4バイト文字列Sを保持します。
When a and b are real numbers, mathematical operators are defined as follows:
aとbが実数の場合、数学演算子は次のように定義されます。
^ : a ^ b denotes the result of a raised to the power of b
* : a * b denotes the product of a multiplied by b
/ : a / b denotes the quotient of a divided by b
% : a % b denotes the remainder of the integer division of a by b (with a and b being restricted to integers in this case)
％：a％bは、aをbで除算した剰余を示します（この場合、aとbは整数に制限されます）
+ : a + b denotes the sum of a and b
- : a - b denotes the difference of a and b
- ：a-bは、aとbの差を示します
AND : a AND b denotes the bitwise AND of the two nonnegative integers a and b (represented in binary notation)
AND：a AND bは、2つの非負整数aとbのビットごとのANDを示します（バイナリ表記で表されます）
The standard order of operations is used when evaluating arithmetic expressions.
演算式を評価するときは、演算の標準的な順序が使用されます。
When B is a byte and i is an integer, then B >> i denotes the logical right-shift operation by i bit positions. Similarly, B << i denotes the logical left-shift operation.
Bがバイトでiが整数の場合、B >> iはiビット位置による論理右シフト演算を示します。同様に、B << iは論理的な左シフト演算を示します。
If S and T are byte strings, then S || T denotes the concatenation of S and T. If S and T are equal-length byte strings, then S AND T denotes the bitwise logical and operation.
SとTがバイト文字列の場合、S || TはSとTの連結を示します。SとTが同じ長さのバイト文字列の場合、S AND Tはビット単位の論理演算と演算を示します。
The i-th element in an array A is denoted as A[i].
配列Aのi番目の要素はA [i]と表されます。
If r is a nonnegative real number, then we define the following functions:
rが負でない実数の場合、次の関数を定義します。
ceil(r) : returns the smallest integer greater than or equal to r
ceil（r）：r以上の最小の整数を返します
floor(r) : returns the largest integer less than or equal to r
floor（r）：r以下の最大の整数を返します
lg(r) : returns the base-2 logarithm of r
lg（r）：rの2を底とする対数を返します
If S is a byte string, then byte(S, i) denotes its i-th byte, where the index starts at 0 at the left. Hence, byte(S, 0) is the leftmost byte of S, byte(S, 1) is the second byte from the left, and (assuming S is n bytes long) byte(S, n-1) is the rightmost byte of S. In addition, bytes(S, i, j) denotes the range of bytes from the i-th to the j-th byte, inclusive. For example, if S = 0x02040608, then byte(S, 0) is 0x02 and bytes(S, 1, 2) is 0x0406.
Sがバイト文字列の場合、byte（S、i）はi番目のバイトを示し、インデックスは左側の0から始まります。したがって、byte（S、0）はSの左端のバイト、byte（S、1）は左から2番目のバイト、そして（Sがnバイトの長さであると仮定して）byte（S、n-1）は右端のバイトです。また、bytes（S、i、j）は、iバイト目からjバイト目までのバイトの範囲を示します。たとえば、S = 0x02040608の場合、byte（S、0）は0x02で、bytes（S、1、2）は0x0406です。
A byte string can be considered to be a string of w-bit unsigned integers; the correspondence is defined by the function coef(S, i, w) as follows:
バイト文字列は、wビットの符号なし整数の文字列と見なすことができます。対応は、関数coef（S、i、w）によって次のように定義されます。
If S is a string, i is a positive integer, and w is a member of the set { 1, 2, 4, 8 }, then coef(S, i, w) is the i-th, w-bit value, if S is interpreted as a sequence of w-bit values. That is,
Sが文字列、iが正の整数、wがセット{1、2、4、8}のメンバーである場合、coef（S、i、w）はi番目のwビット値であり、 Sがwビット値のシーケンスとして解釈される場合。あれは、
coef(S, i, w) = (2^w - 1) AND
( byte(S, floor(i * w / 8)) >>
(8 - (w * (i % (8 / w)) + w)) )
For example, if S is the string 0x1234, then coef(S, 7, 1) is 0 and coef(S, 0, 4) is 1.
たとえば、Sが文字列0x1234の場合、coef（S、7、1）は0で、coef（S、0、4）は1です。
S (represented as bits)
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 0| 0| 0| 1| 0| 0| 1| 0| 0| 0| 1| 1| 0| 1| 0| 0|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
^
|
coef(S, 7, 1)
S (represented as four-bit values)
+-----------+-----------+-----------+-----------+
| 1 | 2 | 3 | 4 |
+-----------+-----------+-----------+-----------+
^
|
coef(S, 0, 4)
The return value of coef is an unsigned integer. If i is larger than the number of w-bit values in S, then coef(S, i, w) is undefined, and an attempt to compute that value MUST raise an error.
coefの戻り値は、符号なし整数です。 iがSのwビット値の数より大きい場合、coef（S、i、w）は未定義であり、その値を計算しようとするとエラーが発生する必要があります。
A typecode is an unsigned integer that is associated with a particular data format. The format of the LM-OTS, LMS, and HSS signatures and public keys all begin with a typecode that indicates the precise details used in that format. These typecodes are represented as four-byte unsigned integers in network byte order; equivalently, they are External Data Representation (XDR) enumerations (see Section 3.3).
タイプコードは、特定のデータ形式に関連付けられている符号なし整数です。 LM-OTS、LMS、およびHSS署名と公開鍵の形式はすべて、その形式で使用される正確な詳細を示すタイプコードで始まります。これらのタイプコードは、ネットワークバイトオーダーの4バイトの符号なし整数として表されます。同様に、それらは外部データ表現（XDR）列挙です（セクション3.3を参照）。
The signature and public key formats are formally defined in XDR to provide an unambiguous, machine-readable definition [RFC4506]. The private key format is not included as it is not needed for interoperability and an implementation MAY use any private key format. However, for clarity, we include an example of private key data in Test Case 2 of Appendix F. Though XDR is used, these formats
署名と公開鍵の形式はXDRで正式に定義されており、明確で機械が読み取り可能な定義を提供しています[RFC4506]。相互運用性のために必要ではないため、プライベートキー形式は含まれていません。実装では、プライベートキー形式を使用できます（MAY）。ただし、わかりやすくするために、付録Fのテストケース2に秘密キーデータの例を含めています。XDRが使用されていますが、これらの形式
are simple and easy to parse without any special tools. An illustration of the layout of data in these objects is provided below. The definitions are as follows:
特別なツールがなくても、シンプルで解析が簡単です。これらのオブジェクトのデータのレイアウトの図を以下に示します。定義は次のとおりです。
/* one-time signatures */
enum lmots_algorithm_type {
lmots_reserved = 0,
lmots_sha256_n32_w1 = 1,
lmots_sha256_n32_w2 = 2,
lmots_sha256_n32_w4 = 3,
lmots_sha256_n32_w8 = 4
};
typedef opaque bytestring32[32];
typedef不透明なバイト文字列32 [32];
struct lmots_signature_n32_p265 {
bytestring32 C;
bytestring32 y[265];
};
struct lmots_signature_n32_p133 {
bytestring32 C;
bytestring32 y[133];
};
struct lmots_signature_n32_p67 {
bytestring32 C;
bytestring32 y[67];
};
struct lmots_signature_n32_p34 {
bytestring32 C;
bytestring32 y[34];
};
union lmots_signature switch (lmots_algorithm_type type) {
case lmots_sha256_n32_w1:
lmots_signature_n32_p265 sig_n32_p265;
case lmots_sha256_n32_w2:
lmots_signature_n32_p133 sig_n32_p133;
case lmots_sha256_n32_w4:
lmots_signature_n32_p67 sig_n32_p67;
case lmots_sha256_n32_w8:
lmots_signature_n32_p34 sig_n32_p34;
default:
void; /* error condition */
};
/* hash-based signatures (hbs) */
enum lms_algorithm_type {
列挙型lms_algorithm_type {
lms_reserved = 0, lms_sha256_n32_h5 = 5, lms_sha256_n32_h10 = 6, lms_sha256_n32_h15 = 7, lms_sha256_n32_h20 = 8, lms_sha256_n32_h25 = 9 };
lms_reserved = 0、lms_sha256_n32_h5 = 5、lms_sha256_n32_h10 = 6、lms_sha256_n32_h15 = 7、lms_sha256_n32_h20 = 8、lms_sha256_n32_h25 = 9};
/* leighton-micali signatures (lms) */
union lms_path switch (lms_algorithm_type type) {
case lms_sha256_n32_h5:
bytestring32 path_n32_h5[5];
case lms_sha256_n32_h10:
bytestring32 path_n32_h10[10];
case lms_sha256_n32_h15:
bytestring32 path_n32_h15[15];
case lms_sha256_n32_h20:
bytestring32 path_n32_h20[20];
case lms_sha256_n32_h25:
bytestring32 path_n32_h25[25];
default:
void; /* error condition */
};
struct lms_signature {
unsigned int q;
lmots_signature lmots_sig;
lms_path nodes;
};
struct lms_key_n32 {
lmots_algorithm_type ots_alg_type;
opaque I[16];
opaque K[32];
};
union lms_public_key switch (lms_algorithm_type type) {
case lms_sha256_n32_h5:
case lms_sha256_n32_h10:
case lms_sha256_n32_h15:
case lms_sha256_n32_h20:
case lms_sha256_n32_h25:
lms_key_n32 z_n32;
default:
void; /* error condition */
};
/* hierarchical signature system (hss) */
struct hss_public_key {
unsigned int L;
lms_public_key pub;
};
struct signed_public_key {
lms_signature sig;
lms_public_key pub;
};
struct hss_signature {
signed_public_key signed_keys<7>;
lms_signature sig_of_message;
};
This section defines LM-OTS signatures. The signature is used to validate the authenticity of a message by associating a secret private key with a shared public key. These are one-time signatures; each private key MUST be used at most one time to sign any given message.
このセクションでは、LM-OTS署名を定義します。署名は、秘密の秘密鍵を共有の公開鍵に関連付けることにより、メッセージの信頼性を検証するために使用されます。これらは1回限りの署名です。各秘密鍵は、特定のメッセージに署名するために、最大で一度使用する必要があります。
As part of the signing process, a digest of the original message is computed using the cryptographic hash function H (see Section 4.1), and the resulting digest is signed.
署名プロセスの一部として、元のメッセージのダイジェストが暗号化ハッシュ関数H（セクション4.1を参照）を使用して計算され、結果のダイジェストが署名されます。
In order to facilitate its use in an N-time signature system, the LM-OTS key generation, signing, and verification algorithms all take as input parameters I and q. The parameter I is a 16-byte string that indicates which Merkle tree this LM-OTS is used with. The parameter q is a 32-bit integer that indicates the leaf of the Merkle tree where the OTS public key appears. These parameters are used as part of the security string, as listed in Section 7.1. When the LM-OTS signature system is used outside of an N-time signature system, the value I MAY be used to differentiate this one-time signature from others; however, the value q MUST be set to the all-zero value.
Nタイム署名システムでの使用を容易にするために、LM-OTS鍵の生成、署名、および検証アルゴリズムはすべて、入力パラメーターIおよびqとして使用されます。パラメータIは、このLM-OTSで使用されるマークルツリーを示す16バイトの文字列です。パラメータqは、OTS公開鍵が表示されるマークルツリーの葉を示す32ビット整数です。これらのパラメータは、セクション7.1に示すように、セキュリティ文字列の一部として使用されます。 LM-OTS署名システムがN回署名システムの外で使用される場合、この1回限りの署名を他の署名と区別するために値Iを使用できます。ただし、値qはすべてゼロの値に設定する必要があります。
The signature system uses the parameters n and w, which are both positive integers. The algorithm description also makes use of the internal parameters p and ls, which are dependent on n and w. These parameters are summarized as follows:
署名システムは、パラメーターnおよびwを使用します。これらは両方とも正の整数です。アルゴリズムの説明では、nとwに依存する内部パラメーターpとlsも使用します。これらのパラメーターは次のように要約されます。
n : the number of bytes of the output of the hash function.
n：ハッシュ関数の出力のバイト数。
w : the width (in bits) of the Winternitz coefficients; that is, the number of bits from the hash or checksum that is used with a single Winternitz chain. It is a member of the set { 1, 2, 4, 8 }.
w：ヴィンターニッツ係数の幅（ビット単位）。つまり、単一のWinternitzチェーンで使用されるハッシュまたはチェックサムからのビット数です。セット{1、2、4、8}のメンバーです。
p : the number of n-byte string elements that make up the LM-OTS signature. This is a function of n and w; the values for the defined parameter sets are listed in Table 1; it can also be computed by the algorithm given in Appendix B.
p：LM-OTS署名を構成するnバイトの文字列要素の数。これはnとwの関数です。定義されたパラメーターセットの値を表1に示します。付録Bに示すアルゴリズムによって計算することもできます。
ls : the number of left-shift bits used in the checksum function Cksm (defined in Section 4.4).
ls：チェックサム関数Cksm（セクション4.4で定義）で使用される左シフトビットの数。
H : a second-preimage-resistant cryptographic hash function that accepts byte strings of any length and returns an n-byte string.
H：2番目のプリイメージ耐性のある暗号化ハッシュ関数。これは、任意の長さのバイト文字列を受け入れ、nバイトの文字列を返します。
For more background on the cryptographic security requirements for H, see Section 9.
Hの暗号化セキュリティ要件の背景については、セクション9を参照してください。
The value of n is determined by the hash function selected for use as part of the LM-OTS algorithm; the choice of this value has a strong effect on the security of the system. The parameter w determines the length of the Winternitz chains computed as a part of the OTS signature (which involve 2^w - 1 invocations of the hash function); it has little effect on security. Increasing w will shorten the signature, but at a cost of a larger computation to generate and verify a signature. The values of p and ls are dependent on the choices of the parameters n and w, as described in Appendix B. Table 1 illustrates various combinations of n, w, p and ls, along with the resulting signature length.
nの値は、LM-OTSアルゴリズムの一部として使用するために選択されたハッシュ関数によって決定されます。この値の選択は、システムのセキュリティに大きな影響を与えます。パラメータwは、OTS署名の一部として計算されたWinternitzチェーンの長さを決定します（ハッシュ関数の2 ^ w-1呼び出しを含みます）。セキュリティにはほとんど影響しません。 wを大きくすると、署名が短くなりますが、署名を生成して検証するための計算が大きくなります。 pとlsの値は、付録Bで説明されているように、パラメーターnとwの選択に依存します。表1は、n、w、p、lsのさまざまな組み合わせと、結果として得られる署名の長さを示しています。
The value of w describes a space/time trade-off; increasing the value of w will cause the signature to shrink (by decreasing the value of p) while increasing the amount of time needed to perform operations with it: generate the public key and generate and verify the signature. In general, the LM-OTS signature is 4+n*(p+1) bytes long, and public key generation will take p*(2^w - 1) + 1 hash computations (and signature generation and verification will take approximately half that on average).
wの値は、空間と時間のトレードオフを表します。 wの値を大きくすると、（pの値を小さくすることによって）署名が縮小し、それを使用して操作を実行するために必要な時間が増加します。一般に、LM-OTS署名の長さは4 + n *（p + 1）バイトで、公開鍵の生成にはp *（2 ^ w-1）+ 1ハッシュ計算が必要です（署名の生成と検証には約半分かかりますその平均）。
+---------------------+--------+----+---+-----+----+---------+
| Parameter Set Name | H | n | w | p | ls | sig_len |
+---------------------+--------+----+---+-----+----+---------+
| LMOTS_SHA256_N32_W1 | SHA256 | 32 | 1 | 265 | 7 | 8516 |
| | | | | | | |
| LMOTS_SHA256_N32_W2 | SHA256 | 32 | 2 | 133 | 6 | 4292 |
| | | | | | | |
| LMOTS_SHA256_N32_W4 | SHA256 | 32 | 4 | 67 | 4 | 2180 |
| | | | | | | |
| LMOTS_SHA256_N32_W8 | SHA256 | 32 | 8 | 34 | 0 | 1124 |
+---------------------+--------+----+---+-----+----+---------+
Table 1
表1
Here SHA256 denotes the SHA-256 hash function defined in NIST standard [FIPS180].
ここで、SHA256は、NIST標準[FIPS180]で定義されているSHA-256ハッシュ関数を表します。
The format of the LM-OTS private key is an internal matter to the implementation, and this document does not attempt to define it. One possibility is that the private key may consist of a typecode indicating the particular LM-OTS algorithm, an array x[] containing p n-byte strings, and the 16-byte string I and the 4-byte string q. This private key MUST be used to sign (at most) one message. The following algorithm shows pseudocode for generating a private key.
LM-OTS秘密鍵の形式は実装の内部の問題であり、このドキュメントではそれを定義しようとはしていません。 1つの可能性は、秘密鍵が、特定のLM-OTSアルゴリズムを示すタイプコード、nバイトの文字列pを含む配列x []、16バイトの文字列Iおよび4バイトの文字列qで構成されていることです。この秘密鍵は、最大で1つのメッセージに署名するために使用する必要があります。次のアルゴリズムは、秘密鍵を生成するための疑似コードを示しています。
Algorithm 0: Generating a Private Key
アルゴリズム0：秘密鍵の生成
1. Retrieve the values of q and I (the 16-byte identifier of the LMS public/private key pair) from the LMS tree that this LM-OTS private key will be used with
1. このLM-OTS秘密鍵が使用されるLMSツリーからqとI（LMS公開/秘密鍵ペアの16バイトの識別子）の値を取得します。
2. Set type to the typecode of the algorithm
2. タイプをアルゴリズムのタイプコードに設定します
3. Set n and p according to the typecode and Table 1
3. タイプコードと表1に従ってnとpを設定します。
4. Compute the array x as follows: for ( i = 0; i < p; i = i + 1 ) { set x[i] to a uniformly random n-byte string }
4. 次のように配列xを計算します。for（i = 0; i <p; i = i + 1）{x [i]を一様にランダムなnバイト文字列に設定}
5. Return u32str(type) || I || u32str(q) || x[0] || x[1] || ... || x[p-1]
5. u32str（type）を返す||私|| u32str（q）|| x [0] || x [1] || ... || x [p-1]
An implementation MAY use a pseudorandom method to compute x[i], as suggested in [Merkle79], page 46. The details of the pseudorandom method do not affect interoperability, but the cryptographic strength MUST match that of the LM-OTS algorithm. Appendix A provides an example of a pseudorandom method for computing the LM-OTS private key.
[Merkle79]、46ページで提案されているように、実装は疑似ランダムメソッドを使用してx [i]を計算できます。疑似ランダムメソッドの詳細は相互運用性に影響しませんが、暗号強度はLM-OTSアルゴリズムの強度と一致する必要があります。付録Aは、LM-OTS秘密鍵を計算するための疑似ランダム方式の例を示しています。
The LM-OTS public key is generated from the private key by iteratively applying the function H to each individual element of x, for 2^w - 1 iterations, then hashing all of the resulting values.
LM-OTS公開鍵は、2 ^ w-1回の反復について、関数Hをxの各要素に繰り返し適用し、結果の値すべてをハッシュすることにより、秘密鍵から生成されます。
The public key is generated from the private key using the following algorithm, or any equivalent process.
公開鍵は、次のアルゴリズムまたは同等のプロセスを使用して秘密鍵から生成されます。
Algorithm 1: Generating a One-Time Signature Public Key From a Private Key
アルゴリズム1：秘密鍵からワンタイム署名公開鍵を生成する
1. Set type to the typecode of the algorithm
1. タイプをアルゴリズムのタイプコードに設定します
2. Set the integers n, p, and w according to the typecode and Table 1
2. タイプコードと表1に従って整数n、p、wを設定します。
3. Determine x, I, and q from the private key
3. 秘密鍵からx、I、qを決定する
4. Compute the string K as follows: for ( i = 0; i < p; i = i + 1 ) { tmp = x[i] for ( j = 0; j < 2^w - 1; j = j + 1 ) { tmp = H(I || u32str(q) || u16str(i) || u8str(j) || tmp) } y[i] = tmp } K = H(I || u32str(q) || u16str(D_PBLC) || y[0] || ... || y[p-1])
4. 文字列Kを次のように計算します：for（i = 0; i <p; i = i + 1）{tmp = x [i] for（j = 0; j <2 ^ w-1; j = j + 1） {tmp = H（I || u32str（q）|| u16str（i）|| u8str（j）|| tmp）} y [i] = tmp} K = H（I || u32str（q）|| u16str （D_PBLC）|| y [0] || ... || y [p-1]）
5. Return u32str(type) || I || u32str(q) || K
5. u32str（type）を返す||私|| u32str（q）|| K
where D_PBLC is the fixed two-byte value 0x8080, which is used to distinguish the last hash from every other hash in this system.
ここで、D_PBLCは2バイトの固定値0x8080で、このシステムで最後のハッシュと他のすべてのハッシュを区別するために使用されます。
The public key is the value returned by Algorithm 1.
公開鍵は、アルゴリズム1によって返される値です。
A checksum is used to ensure that any forgery attempt that manipulates the elements of an existing signature will be detected. This checksum is needed because an attacker can freely advance any of the Winternitz chains. That is, if this checksum were not present, then an attacker who could find a hash that has every digit larger than the valid hash could replace it (and adjust the Winternitz chains). The security property that the checksum provides is detailed in Section 9. The checksum function Cksm is defined as follows, where S denotes the n-byte string that is input to that function, and the value sum is a 16-bit unsigned integer:
チェックサムは、既存の署名の要素を操作する偽造の試みが確実に検出されるようにするために使用されます。攻撃者は任意のWinternitzチェーンを自由に進めることができるため、このチェックサムが必要です。つまり、このチェックサムが存在しない場合、有効なハッシュよりもすべての桁が大きいハッシュを見つけることができる攻撃者は、それを置き換える（そしてWinternitzチェーンを調整する）ことができる。チェックサムが提供するセキュリティプロパティについては、セクション9で詳しく説明します。チェックサム関数Cksmは次のように定義されます。Sはその関数に入力されるnバイトの文字列を示し、値の合計は16ビットの符号なし整数です。
Algorithm 2: Checksum Calculation
アルゴリズム2：チェックサムの計算
sum = 0
for ( i = 0; i < (n*8/w); i = i + 1 ) {
sum = sum + (2^w - 1) - coef(S, i, w)
}
return (sum << ls)
ls is the parameter that shifts the significant bits of the checksum into the positions that will actually be used by the coef function when encoding the digits of the checksum. The actual ls parameter is a function of the n and w parameters; the values for the currently defined parameter sets are shown in Table 1. It is calculated by the algorithm given in Appendix B.
lsは、チェックサムの有効ビットを、チェックサムの数字をエンコードするときにcoef関数によって実際に使用される位置にシフトするパラメーターです。実際のlsパラメータは、nおよびwパラメータの関数です。現在定義されているパラメータセットの値を表1に示します。この値は、付録Bに示されているアルゴリズムによって計算されます。
Because of the left-shift operation, the rightmost bits of the result of Cksm will often be zeros. Due to the value of p, these bits will not be used during signature generation or verification.
左シフト演算のため、Cksmの結果の右端のビットは多くの場合ゼロになります。 pの値により、これらのビットは署名の生成または検証中に使用されません。
The LM-OTS signature of a message is generated by doing the following in sequence: prepending the LMS key identifier I, the LMS leaf identifier q, the value D_MESG (0x8181), and the randomizer C to the message; computing the hash; concatenating the checksum of the hash to the hash itself; considering the resulting value as a sequence of w-bit values; and using each of the w-bit values to determine the number of times to apply the function H to the corresponding element of the private key. The outputs of the function H are concatenated together and returned as the signature. The pseudocode for this procedure is shown below.
メッセージのLM-OTSシグネチャは、次の手順を順に実行することによって生成されます。LMSキー識別子I、LMSリーフ識別子q、値D_MESG（0x8181）、およびランダマイザーCをメッセージの前に付加します。ハッシュを計算する;ハッシュのチェックサムをハッシュ自体に連結します。結果の値をwビット値のシーケンスと見なします。そして、各wビット値を使用して、秘密鍵の対応する要素に関数Hを適用する回数を決定します。関数Hの出力は連結され、署名として返されます。この手順の疑似コードを以下に示します。
Algorithm 3: Generating a One-Time Signature From a Private Key and a Message
アルゴリズム3：秘密鍵とメッセージからワンタイム署名を生成する
1. Set type to the typecode of the algorithm
1. タイプをアルゴリズムのタイプコードに設定します
2. Set n, p, and w according to the typecode and Table 1
2. タイプコードと表1に従って、n、p、wを設定します。
3. Determine x, I, and q from the private key
3. 秘密鍵からx、I、qを決定する
4. Set C to a uniformly random n-byte string
5. Compute the array y as follows:
Q = H(I || u32str(q) || u16str(D_MESG) || C || message)
for ( i = 0; i < p; i = i + 1 ) {
a = coef(Q || Cksm(Q), i, w)
tmp = x[i]
for ( j = 0; j < a; j = j + 1 ) {
tmp = H(I || u32str(q) || u16str(i) || u8str(j) || tmp)
}
y[i] = tmp
}
6. Return u32str(type) || C || y[0] || ... || y[p-1]
6. u32str（type）を返す|| C || y [0] || ... || y [p-1]
Note that this algorithm results in a signature whose elements are intermediate values of the elements computed by the public key algorithm in Section 4.3.
このアルゴリズムでは、4.3節の公開鍵アルゴリズムによって計算された要素の中間値を要素とする署名が生成されることに注意してください。
The signature is the string returned by Algorithm 3. Section 3.3 formally defines the structure of the string as the lmots_signature union.
署名は、アルゴリズム3によって返される文字列です。セクション3.3では、文字列の構造をlmots_signature共用体として正式に定義しています。
In order to verify a message with its signature (an array of n-byte strings, denoted as y), the receiver must "complete" the chain of iterations of H using the w-bit coefficients of the string resulting from the concatenation of the message hash and its checksum. This computation should result in a value that matches the provided public key.
メッセージを署名（nバイト文字列の配列、yと表記）で検証するには、受信側は、Hの連結の結果として得られる文字列のwビット係数を使用して、Hの反復のチェーンを「完了する」必要があります。メッセージハッシュとそのチェックサム。この計算により、提供された公開鍵と一致する値が得られます。
Algorithm 4a: Verifying a Signature and Message Using a Public Key
アルゴリズム4a：公開鍵を使用して署名とメッセージを検証する
1. If the public key is not at least four bytes long, return INVALID.
1. 公開鍵の長さが4バイト以上でない場合は、INVALIDを返します。
2. Parse pubtype, I, q, and K from the public key as follows: a. pubtype = strTou32(first 4 bytes of public key)
2. 次のように、公開鍵からpubtype、I、q、およびKを解析します。 pubtype = strTou32（公開鍵の最初の4バイト）
b. Set n according to the pubkey and Table 1; if the public key is not exactly 24 + n bytes long, return INVALID.
b. pubkeyと表1に従ってnを設定します。公開鍵の長さが正確に24 + nバイトでない場合は、INVALIDを返します。
c. I = next 16 bytes of public key
c. I =公開鍵の次の16バイト
d. q = strTou32(next 4 bytes of public key)
d. q = strTou32（公開鍵の次の4バイト）
e. K = next n bytes of public key
e. K =公開鍵の次のnバイト
3. Compute the public key candidate Kc from the signature, message, pubtype, and the identifiers I and q obtained from the public key, using Algorithm 4b. If Algorithm 4b returns INVALID, then return INVALID.
3. アルゴリズム4bを使用して、署名、メッセージ、pubtype、および公開鍵から取得した識別子Iとqから公開鍵候補Kcを計算します。アルゴリズム4bがINVALIDを返す場合、INVALIDを返します。
4. If Kc is equal to K, return VALID; otherwise, return INVALID.
4. KcがKと等しい場合、VALIDを返します。それ以外の場合は、INVALIDを返します。
Algorithm 4b: Computing a Public Key Candidate Kc from a Signature, Message, Signature Typecode pubtype, and Identifiers I, q
アルゴリズム4b：署名、メッセージ、署名タイプコードpubtype、および識別子I、qから公開鍵候補Kcを計算する
1. If the signature is not at least four bytes long, return INVALID.
1. 署名の長さが4バイト以上でない場合は、INVALIDを返します。
2. Parse sigtype, C, and y from the signature as follows: a. sigtype = strTou32(first 4 bytes of signature)
2. 次のように署名からsigtype、C、およびyを解析します。 sigtype = strTou32（署名の最初の4バイト）
b. If sigtype is not equal to pubtype, return INVALID.
b. sigtypeがpubtypeと等しくない場合は、INVALIDを返します。
c. Set n and p according to the pubtype and Table 1; if the signature is not exactly 4 + n * (p+1) bytes long, return INVALID.
c. pubtypeおよび表1に従ってnおよびpを設定します。署名の長さが4 + n *（p + 1）バイトでない場合は、INVALIDを返します。
d. C = next n bytes of signature
d. C =次のnバイトの署名
e. y[0] = next n bytes of signature y[1] = next n bytes of signature ... y[p-1] = next n bytes of signature
e. y [0] =署名の次のnバイトy [1] =署名の次のnバイト... y [p-1] =署名の次のnバイト
3. Compute the string Kc as follows: Q = H(I || u32str(q) || u16str(D_MESG) || C || message) for ( i = 0; i < p; i = i + 1 ) { a = coef(Q || Cksm(Q), i, w) tmp = y[i] for ( j = a; j < 2^w - 1; j = j + 1 ) { tmp = H(I || u32str(q) || u16str(i) || u8str(j) || tmp) } z[i] = tmp } Kc = H(I || u32str(q) || u16str(D_PBLC) || z[0] || z[1] || ... || z[p-1])
3. 次のように文字列Kcを計算します。Q= H（I || u32str（q）|| u16str（D_MESG）|| C || message）for（i = 0; i <p; i = i + 1）{a = coef（Q || Cksm（Q）、i、w）tmp = y [i] for（j = a; j <2 ^ w-1; j = j + 1）{tmp = H（I || u32str（ q）|| u16str（i）|| u8str（j）|| tmp）} z [i] = tmp} Kc = H（I || u32str（q）|| u16str（D_PBLC）|| z [0] | | z [1] || ... || z [p-1]）
4. Return Kc.
4. Kcを返します。
The Leighton-Micali Signature (LMS) method can sign a potentially large but fixed number of messages. An LMS system uses two cryptographic components: a one-time signature method and a hash function. Each LMS public/private key pair is associated with a perfect binary tree, each node of which contains an m-byte value, where m is the output length of the hash function. Each leaf of the tree contains the value of the public key of an LM-OTS public/private key pair. The value contained by the root of the tree is the LMS public key. Each interior node is computed by applying the hash function to the concatenation of the values of its children nodes.
Leighton-Micali Signature（LMS）メソッドは、潜在的に大きいが固定数のメッセージに署名できます。 LMSシステムは、1回限りの署名方式とハッシュ関数の2つの暗号化コンポーネントを使用します。各LMS公開/秘密鍵のペアは完全なバイナリツリーに関連付けられており、その各ノードにはmバイトの値が含まれています。mはハッシュ関数の出力長です。ツリーの各リーフには、LM-OTS公開/秘密鍵ペアの公開鍵の値が含まれています。ツリーのルートに含まれる値はLMS公開鍵です。各内部ノードは、その子ノードの値の連結にハッシュ関数を適用することによって計算されます。
Each node of the tree is associated with a node number, an unsigned integer that is denoted as node_num in the algorithms below, which is computed as follows. The root node has node number 1; for each node with node number N < 2^h (where h is the height of the tree), its left child has node number 2*N, while its right child has node number 2*N + 1. The result of this is that each node within the tree will have a unique node number, and the leaves will have node numbers 2^h, (2^h)+1, (2^h)+2, ..., (2^h)+(2^h)-1. In general, the j-th node at level i has node number 2^i + j. The node number can conveniently be computed when it is needed in the LMS algorithms, as described in those algorithms.
ツリーの各ノードはノード番号に関連付けられています。これは、以下のように計算される以下のアルゴリズムでnode_numとして示される符号なし整数です。ルートノードのノード番号は1です。ノード番号N <2 ^ h（hはツリーの高さ）の各ノードについて、その左側の子はノード番号2 * N、右側の子はノード番号2 * N + 1です。この結果はツリー内の各ノードには一意のノード番号があり、葉にはノード番号2 ^ h、（2 ^ h）+1、（2 ^ h）+2、...、（2 ^ h）+があります。 （2 ^ h）-1。一般に、レベルiのj番目のノードのノード番号は2 ^ i + jです。ノード番号は、アルゴリズムで説明されているように、LMSアルゴリズムで必要なときに便利に計算できます。
An LMS system has the following parameters:
LMSシステムには次のパラメーターがあります。
h : the height of the tree
h：木の高さ
m : the number of bytes associated with each node
m：各ノードに関連付けられているバイト数
H : a second-preimage-resistant cryptographic hash function that accepts byte strings of any length and returns an m-byte string.
H：2番目のプリイメージ耐性のある暗号化ハッシュ関数。これは、任意の長さのバイト文字列を受け入れ、mバイトの文字列を返します。
There are 2^h leaves in the tree.
ツリーには2 ^ hの葉があります。
The overall strength of LMS signatures is governed by the weaker of the hash function used within the LM-OTS and the hash function used within the LMS system. In order to minimize the risk, these two hash functions SHOULD be the same (so that an attacker could not take advantage of the weaker hash function choice).
LMSシグネチャの全体的な強度は、LM-OTS内で使用されるハッシュ関数とLMSシステム内で使用されるハッシュ関数の弱い方によって制御されます。リスクを最小限に抑えるために、これら2つのハッシュ関数は同じである必要があります（攻撃者がより弱いハッシュ関数の選択を利用できないようにするため）。
+--------------------+--------+----+----+
| Name | H | m | h |
+--------------------+--------+----+----+
| LMS_SHA256_M32_H5 | SHA256 | 32 | 5 |
| | | | |
| LMS_SHA256_M32_H10 | SHA256 | 32 | 10 |
| | | | |
| LMS_SHA256_M32_H15 | SHA256 | 32 | 15 |
| | | | |
| LMS_SHA256_M32_H20 | SHA256 | 32 | 20 |
| | | | |
| LMS_SHA256_M32_H25 | SHA256 | 32 | 25 |
+--------------------+--------+----+----+
Table 2
表2
The format of the LMS private key is an internal matter to the implementation, and this document does not attempt to define it. One possibility is that it may consist of an array OTS_PRIV[] of 2^h LM-OTS private keys and the leaf number q of the next LM-OTS private key that has not yet been used. The q-th element of OTS_PRIV[] is generated using Algorithm 0 with the identifiers I, q. The leaf number q is initialized to zero when the LMS private key is created. The process is as follows:
LMS秘密鍵の形式は実装の内部の問題であり、このドキュメントではそれを定義しようとはしていません。 1つの可能性は、2 ^ h LM-OTS秘密鍵の配列OTS_PRIV []と、まだ使用されていない次のLM-OTS秘密鍵のリーフ番号qで構成される可能性があります。 OTS_PRIV []のq番目の要素は、識別子I、qとともにアルゴリズム0を使用して生成されます。リーフ番号qは、LMS秘密鍵が作成されるときにゼロに初期化されます。プロセスは次のとおりです。
Algorithm 5: Computing an LMS Private Key.
アルゴリズム5：LMS秘密鍵の計算。
1. Determine h and m from the typecode and Table 2.
1. タイプコードと表2からhとmを決定します。
2. Set I to a uniformly random 16-byte string.
2. Iを一様にランダムな16バイト文字列に設定します。
3. Compute the array OTS_PRIV[] as follows: for ( q = 0; q < 2^h; q = q + 1) { OTS_PRIV[q] = LM-OTS private key with identifiers I, q }
3. 配列OTS_PRIV []を次のように計算します。for（q = 0; q <2 ^ h; q = q + 1）{OTS_PRIV [q] = LM-OTS秘密キー、識別子I、q}
4. q = 0
4. q = 0
An LMS private key MAY be generated pseudorandomly from a secret value; in this case, the secret value MUST be at least m bytes long and uniformly random and MUST NOT be used for any other purpose than the generation of the LMS private key. The details of how this process is done do not affect interoperability; that is, the public key verification operation is independent of these details. Appendix A provides an example of a pseudorandom method for computing an LMS private key.
LMS秘密鍵は、秘密の値から擬似ランダムに生成される場合があります。この場合、秘密の値は少なくともmバイトの長さで均一にランダムでなければならず、LMS秘密鍵の生成以外の目的で使用してはならない（MUST NOT）。このプロセスの実行方法の詳細は、相互運用性には影響しません。つまり、公開鍵の検証操作は、これらの詳細から独立しています。付録Aは、LMS秘密鍵を計算するための疑似ランダム方式の例を示しています。
The signature-generation logic uses q as the next leaf to use; hence, step 4 starts it off at the leftmost leaf. Because the signature process increments q after the signature operation, the first signature will have q=0.
署名生成ロジックは、使用する次のリーフとしてqを使用します。したがって、ステップ4では、一番左の葉から開始します。署名プロセスは署名操作後にqを増分するため、最初の署名はq = 0になります。
An LMS public key is defined as follows, where we denote the public key final hash value (namely, the K value computed in Algorithm 1) associated with the i-th LM-OTS private key as OTS_PUB_HASH[i], with i ranging from 0 to (2^h)-1. Each instance of an LMS public/private key pair is associated with a balanced binary tree, and the nodes of that tree are indexed from 1 to 2^(h+1)-1. Each node is associated with an m-byte string. The string for the r-th node is denoted as T[r] and defined as
LMS公開鍵は次のように定義されます。ここで、i番目のLM-OTS秘密鍵に関連付けられた公開鍵の最終ハッシュ値（つまり、アルゴリズム1で計算されたK値）をOTS_PUB_HASH [i]として表します。 0から（2 ^ h）-1。 LMS公開/秘密鍵ペアの各インスタンスは、平衡型バイナリツリーに関連付けられており、そのツリーのノードには1から2 ^（h + 1）-1までのインデックスが付けられています。各ノードはmバイトの文字列に関連付けられています。 r番目のノードの文字列はT [r]として示され、次のように定義されます。
if r >= 2^h:
H(I||u32str(r)||u16str(D_LEAF)||OTS_PUB_HASH[r-2^h])
else
H(I||u32str(r)||u16str(D_INTR)||T[2*r]||T[2*r+1])
where D_LEAF is the fixed two-byte value 0x8282 and D_INTR is the fixed two-byte value 0x8383, both of which are used to distinguish this hash from every other hash in this system.
ここで、D_LEAFは固定2バイト値0x8282で、D_INTRは固定2バイト値0x8383です。どちらも、このハッシュをこのシステムの他のすべてのハッシュと区別するために使用されます。
When we have r >= 2^h, then we are processing a leaf node (and thus hashing only a single LM-OTS public key). When we have r < 2^h, then we are processing an internal node -- that is, a node with two child nodes that we need to combine.
r> = 2 ^ hの場合、リーフノードを処理しています（したがって、単一のLM-OTS公開鍵のみをハッシュします）。 r <2 ^ hの場合、内部ノード、つまり結合する必要がある2つの子ノードを持つノードを処理しています。
The LMS public key can be represented as the byte string
LMS公開鍵はバイト文字列として表すことができます
u32str(type) || u32str(otstype) || I || T[1]
u32str（タイプ）|| u32str（otstype）||私|| T [1]
Section 3.3 specifies the format of the type variable. The value otstype is the parameter set for the LM-OTS public/private key pairs used. The value I is the private key identifier and is the value used for all computations for the same LMS tree. The value T[1] can be computed via recursive application of the above equation or by any equivalent method. An iterative procedure is outlined in Appendix C.
セクション3.3では、タイプ変数の形式を指定します。値otstypeは、使用されるLM-OTS公開/秘密鍵ペアのパラメーターセットです。値Iは秘密鍵識別子であり、同じLMSツリーのすべての計算に使用される値です。値T [1]は、上記の方程式を再帰的に適用するか、同等の方法で計算できます。反復手順の概要は、付録Cにあります。
An LMS signature consists of
LMS署名は、
the number q of the leaf associated with the LM-OTS signature, as a four-byte unsigned integer in network byte order, an LM-OTS signature,
LM-OTS署名に関連付けられたリーフの番号q。ネットワークバイトオーダーの4バイトの符号なし整数、LM-OTS署名、
a typecode indicating the particular LMS algorithm,
特定のLMSアルゴリズムを示すタイプコード
an array of h m-byte values that is associated with the path through the tree from the leaf associated with the LM-OTS signature to the root.
LM-OTSシグネチャに関連付けられたリーフからルートへのツリーのパスに関連付けられたh mバイト値の配列。
Symbolically, the signature can be represented as
象徴的に、署名は次のように表すことができます
u32str(q) || lmots_signature || u32str(type) || path[0] || path[1] || path[2] || ... || path[h-1]
u32str（q）|| lmots_signature || u32str（タイプ）||パス[0] ||パス[1] ||パス[2] || ... ||パス[h-1]
Section 3.3 formally defines the format of the signature as the lms_signature structure. The array for a tree with height h will have h values and contains the values of the siblings of (that is, is adjacent to) the nodes on the path from the leaf to the root, where the sibling to node A is the other node that shares node A's parent. In the signature, 0 is counted from the bottom level of the tree, and so path[0] is the value of the node adjacent to leaf node q; path[1] is the second-level node that is adjacent to leaf node q's parent, and so on up the tree until we get to path[h-1], which is the value of the next-to-the-top-level node whose branch the leaf node q does not reside in.
セクション3.3では、署名の形式をlms_signature構造として正式に定義しています。高さhのツリーの配列はh値を持ち、葉からルートへのパス上のノードの兄弟の値を含みます（つまり、ノードAの兄弟は他のノードです）。ノードAの親を共有します。シグネチャでは、0はツリーの最下位レベルから数えられるため、path [0]はリーフノードqに隣接するノードの値です。 path [1]は、リーフノードqの親に隣接する2番目のレベルのノードであり、path-h-the-top-the-top-リーフノードqが存在しないブランチを持つレベルノード。
Below is a simple example of the authentication path for h=3 and q=2. The leaf marked OTS is the one-time signature that is used to sign the actual message. The nodes on the path from the OTS public key to the root are marked with a *, while the nodes that are used within the path array are marked with **. The values in the path array are those nodes that are siblings of the nodes on the path; path[0] is the leaf** node that is adjacent to the OTS public key (which is the start of the path); path[1] is the T[4]** node that is the sibling of the second node T[5]* on the path, and path[2] is the T[3]** node that is the sibling of the third node T[2]* on the path.
以下は、h = 3およびq = 2の認証パスの簡単な例です。リーフとマークされたOTSは、実際のメッセージに署名するために使用される1回限りの署名です。 OTS公開鍵からルートへのパス上のノードは*でマークされ、パス配列内で使用されるノードは**でマークされます。パス配列の値は、パス上のノードの兄弟であるノードです。 path [0]は、OTS公開鍵（パスの始まり）に隣接するleaf **ノードです。 path [1]はパス上の2番目のノードT [5] *の兄弟であるT [4] **ノードであり、path [2]はパスの兄弟であるT [3] **ノードですパス上の3番目のノードT [2] *。
Root
|
---------------------------------
| |
T[2]* T[3]**
| |
------------------ -----------------
| | | |
T[4]** T[5]* T[6] T[7]
| | | |
--------- ---------- -------- ---------
| | | | | | | |
leaf leaf OTS leaf** leaf leaf leaf leaf
The idea behind this authentication path is that it allows us to validate the OTS hash with using h path array values and hash computations. What the verifier does is recompute the hashes up the path; first, it hashes the given OTS and path[0] value, giving a tentative T[5]' value. Then, it hashes its path[1] and tentative T[5]' value to get a tentative T[2]' value. Then, it hashes that and the path[2] value to get a tentative Root' value. If that value is the known public key of the Merkle tree, then we can assume that the value T[2]' it got was the correct T[2] value in the original tree, and so the T[5]' value it got was the correct T[5] value in the original tree, and so the OTS public key is the same as in the original and, hence, is correct.
この認証パスの背後にある考え方は、hパス配列値とハッシュ計算を使用してOTSハッシュを検証できるようにすることです。ベリファイアが行うことは、パスのハッシュを再計算することです。まず、指定されたOTSとpath [0]の値をハッシュして、暫定的なT [5] 'の値を与えます。次に、path [1]と仮のT [5] '値をハッシュして、仮のT [2]'値を取得します。次に、それとpath [2]値をハッシュして、仮のRoot値を取得します。その値がマークルツリーの既知の公開鍵である場合、取得した値T [2] 'は元のツリーの正しいT [2]値であったと見なすことができるため、T [5]'の値はgotは元のツリーの正しいT [5]値だったため、OTS公開鍵は元のツリーと同じであり、したがって正しいです。
To compute the LMS signature of a message with an LMS private key, the signer first computes the LM-OTS signature of the message using the leaf number of the next unused LM-OTS private key. The leaf number q in the signature is set to the leaf number of the LMS private key that was used in the signature. Before releasing the signature, the leaf number q in the LMS private key MUST be incremented to prevent the LM-OTS private key from being used again. If the LMS private key is maintained in nonvolatile memory, then the implementation MUST ensure that the incremented value has been stored before releasing the signature. The issue this tries to prevent is a scenario where a) we generate a signature using one LM-OTS private key and release it to the application, b) before we update the nonvolatile memory, we crash, and c) we reboot and generate a second signature using the same LM-OTS private key. With two different signatures using the same LM-OTS private key, an attacker could potentially generate a forged signature of a third message.
LMS秘密鍵を使用してメッセージのLMS署名を計算するには、署名者はまず、次の未使用のLM-OTS秘密鍵のリーフ番号を使用してメッセージのLM-OTS署名を計算します。署名のリーフ番号qは、署名で使用されたLMS秘密鍵のリーフ番号に設定されます。署名を解放する前に、LM-OTS秘密鍵が再び使用されないように、LMS秘密鍵のリーフ番号qをインクリメントする必要があります。 LMS秘密鍵が不揮発性メモリに保持されている場合、実装は、署名を解放する前に、増分された値が格納されていることを確認する必要があります。これが防止しようとする問題は、a）1つのLM-OTS秘密鍵を使用して署名を生成し、それをアプリケーションにリリースするシナリオ、b）不揮発性メモリを更新する前にクラッシュする、c）再起動して生成するシナリオです。同じLM-OTS秘密鍵を使用する2番目の署名。同じLM-OTS秘密鍵を使用する2つの異なる署名があると、攻撃者は3番目のメッセージの偽造署名を生成する可能性があります。
The array of node values in the signature MAY be computed in any way. There are many potential time/storage trade-offs that can be applied. The fastest alternative is to store all of the nodes of the tree and set the array in the signature by copying them; pseudocode to do so appears in Appendix D. The least storage-intensive alternative is to recompute all of the nodes for each signature. Note that the details of this procedure are not important for interoperability; it is not necessary to know any of these details in order to perform the signature-verification operation. The internal nodes of the tree need not be kept secret, and thus a node-caching scheme that stores only internal nodes can sidestep the need for strong protections.
シグネチャ内のノード値の配列は、任意の方法で計算される場合があります。適用できる時間/ストレージのトレードオフは数多くあります。最速の代替案は、ツリーのすべてのノードを格納し、それらをコピーしてシグニチャーに配列を設定することです。そうするための疑似コードは、付録Dにあります。最もストレージを集中的に使用しない方法は、各シグネチャのすべてのノードを再計算することです。この手順の詳細は相互運用性にとって重要ではないことに注意してください。署名検証操作を実行するために、これらの詳細を知る必要はありません。ツリーの内部ノードは秘密にしておく必要がないため、内部ノードのみを格納するノードキャッシュスキームは、強力な保護の必要性を回避できます。
Several useful time/storage trade-offs are described in the "Small-Memory LM Schemes" section of [USPTO5432852].
いくつかの有用な時間とストレージのトレードオフは、[USPTO5432852]の「Small-Memory LM Schemes」セクションで説明されています。
An LMS signature is verified by first using the LM-OTS signature verification algorithm (Algorithm 4b) to compute the LM-OTS public key from the LM-OTS signature and the message. The value of that public key is then assigned to the associated leaf of the LMS tree, and then the root of the tree is computed from the leaf value and the array path[] as described in Algorithm 6 below. If the root value matches the public key, then the signature is valid; otherwise, the signature verification fails.
LMS署名は、最初にLM-OTS署名検証アルゴリズム（アルゴリズム4b）を使用して、LM-OTS署名とメッセージからLM-OTS公開鍵を計算することによって検証されます。次に、その公開鍵の値がLMSツリーの関連する葉に割り当てられ、次に、以下のアルゴリズム6で説明するように、葉の値と配列path []からツリーのルートが計算されます。ルート値が公開鍵と一致する場合、署名は有効です。そうでない場合、署名の検証は失敗します。
Algorithm 6: LMS Signature Verification
アルゴリズム6：LMS署名の検証
1. If the public key is not at least eight bytes long, return INVALID.
1. 公開鍵の長さが8バイト以上でない場合は、INVALIDを返します。
2. Parse pubtype, I, and T[1] from the public key as follows:
2. 次のように、公開鍵からpubtype、I、およびT [1]を解析します。
a. pubtype = strTou32(first 4 bytes of public key)
a. pubtype = strTou32（公開鍵の最初の4バイト）
b. ots_typecode = strTou32(next 4 bytes of public key)
b. ots_typecode = strTou32（公開鍵の次の4バイト）
c. Set m according to pubtype, based on Table 2.
c. 表2に基づいて、pubtypeに従ってmを設定します。
d. If the public key is not exactly 24 + m bytes long, return INVALID.
d. 公開鍵の長さが正確に24 + mバイトでない場合は、INVALIDを返します。
e. I = next 16 bytes of the public key
e. I =公開鍵の次の16バイト
f. T[1] = next m bytes of the public key
f. T [1] =公開鍵の次のmバイト
3. Compute the LMS Public Key Candidate Tc from the signature, message, identifier, pubtype, and ots_typecode, using Algorithm 6a.
3. アルゴリズム6aを使用して、署名、メッセージ、識別子、pubtype、およびots_typecodeからLMS公開鍵候補Tcを計算します。
4. If Tc is equal to T[1], return VALID; otherwise, return INVALID.
4. TcがT [1]と等しい場合、VALIDを返します。それ以外の場合は、INVALIDを返します。
Algorithm 6a: Computing an LMS Public Key Candidate from a Signature, Message, Identifier, and Algorithm Typecodes
アルゴリズム6a：署名、メッセージ、識別子、アルゴリズムタイプコードからLMS公開鍵候補を計算する
1. If the signature is not at least eight bytes long, return INVALID.
1. 署名の長さが8バイト以上でない場合は、INVALIDを返します。
2. Parse sigtype, q, lmots_signature, and path from the signature as follows:
2. sigtype、q、lmots_signature、および署名からのパスを次のように解析します。
a. q = strTou32(first 4 bytes of signature)
a. q = strTou32（署名の最初の4バイト）
b. otssigtype = strTou32(next 4 bytes of signature)
b. otssigtype = strTou32（次の4バイトの署名）
c. If otssigtype is not the OTS typecode from the public key, return INVALID.
c. otssigtypeが公開鍵のOTSタイプコードでない場合は、INVALIDを返します。
d. Set n, p according to otssigtype and Table 1; if the signature is not at least 12 + n * (p + 1) bytes long, return INVALID.
d. otssigtypeおよび表1に従ってn、pを設定します。署名の長さが12 + n *（p + 1）バイト以上でない場合は、INVALIDを返します。
e. lmots_signature = bytes 4 through 7 + n * (p + 1)
of signature
f. sigtype = strTou32(bytes 8 + n * (p + 1)) through
11 + n * (p + 1) of signature)
g. If sigtype is not the LM typecode from the public key, return INVALID.
g. sigtypeが公開鍵のLMタイプコードでない場合は、INVALIDを返します。
h. Set m, h according to sigtype and Table 2.
h. sigtypeおよび表2に従って、m、hを設定します。
i. If q >= 2^h or the signature is not exactly 12 + n * (p + 1) + m * h bytes long, return INVALID.
i. q> = 2 ^ hであるか、署名が12 + n *（p + 1）+ m * hバイト長でない場合、INVALIDを返します。
j. Set path as follows: path[0] = next m bytes of signature path[1] = next m bytes of signature ... path[h-1] = next m bytes of signature
j. パスを次のように設定します。path[0] =署名の次のmバイトpath [1] =署名の次のmバイト... path [h-1] =署名の次のmバイト
3. Kc = candidate public key computed by applying Algorithm 4b to the signature lmots_signature, the message, and the identifiers I, q
3. Kc =アルゴリズム4bを署名lmots_signature、メッセージ、および識別子I、qに適用して計算された候補公開鍵
4. Compute the candidate LMS root value Tc as follows: node_num = 2^h + q tmp = H(I || u32str(node_num) || u16str(D_LEAF) || Kc) i = 0 while (node_num > 1) { if (node_num is odd): tmp = H(I||u32str(node_num/2)||u16str(D_INTR)||path[i]||tmp) else: tmp = H(I||u32str(node_num/2)||u16str(D_INTR)||tmp||path[i]) node_num = node_num/2 i = i + 1 } Tc = tmp
4. 次のように候補LMSルート値Tcを計算します。node_num = 2 ^ h + q tmp = H（I || u32str（node_num）|| u16str（D_LEAF）|| Kc）i = 0 while（node_num> 1）{if（if node_numは奇数です）：tmp = H（I || u32str（node_num / 2）|| u16str（D_INTR）|| path [i] || tmp）else：tmp = H（I || u32str（node_num / 2）| | u16str（D_INTR）|| tmp || path [i]）node_num = node_num / 2 i = i + 1} Tc = tmp
5. Return Tc.
5. Tcを返します。
In scenarios where it is necessary to minimize the time taken by the public key generation process, the Hierarchical Signature System (HSS) can be used. This hierarchical scheme, which we describe in this section, uses the LMS scheme as a component. In HSS, we have a sequence of L LMS trees, where the public key for the first LMS tree is included in the public key of the HSS system, each LMS private key signs the next LMS public key, and the last LMS private key signs the actual message. For example, if we have a three-level hierarchy (L=3), then to sign a message, we would have:
公開鍵生成プロセスにかかる時間を最小限に抑える必要があるシナリオでは、階層署名システム（HSS）を使用できます。このセクションで説明するこの階層方式は、LMS方式をコンポーネントとして使用します。 HSSには、L LMSツリーのシーケンスがあり、最初のLMSツリーの公開鍵はHSSシステムの公開鍵に含まれ、各LMS秘密鍵は次のLMS公開鍵に署名し、最後のLMS秘密鍵は署名します実際のメッセージ。たとえば、3レベルの階層（L = 3）がある場合、メッセージに署名するには、次のようにします。
The first LMS private key (level 0) signs a level 1 LMS public key.
最初のLMS秘密鍵（レベル0）は、レベル1のLMS公開鍵に署名します。
The second LMS private key (level 1) signs a level 2 LMS public key.
2番目のLMS秘密鍵（レベル1）は、レベル2のLMS公開鍵に署名します。
The third LMS private key (level 2) signs the message.
3番目のLMS秘密鍵（レベル2）がメッセージに署名します。
The root of the level 0 LMS tree is contained in the HSS public key.
レベル0のLMSツリーのルートは、HSS公開鍵に含まれています。
To verify the LMS signature, we would verify all the signatures:
LMS署名を検証するには、すべての署名を検証します。
We would verify that the level 1 LMS public key is correctly signed by the level 0 signature.
レベル1のLMS公開鍵がレベル0の署名によって正しく署名されていることを確認します。
We would verify that the level 2 LMS public key is correctly signed by the level 1 signature.
レベル2のLMS公開鍵がレベル1の署名によって正しく署名されていることを確認します。
We would verify that the message is correctly signed by the level 2 signature.
メッセージがレベル2の署名によって正しく署名されていることを確認します。
We would accept the HSS signature only if all the signatures validated.
すべての署名が検証された場合にのみ、HSS署名を受け入れます。
During the signature-generation process, we sign messages with the lowest (level L-1) LMS tree. Once we have used all the leafs in that tree to sign messages, we would discard it, generate a fresh LMS tree, and sign it with the next (level L-2) LMS tree (and when that is used up, recursively generate and sign a fresh level L-2 LMS tree).
署名生成プロセスでは、最下位（レベルL-1）のLMSツリーでメッセージに署名します。そのツリーのすべての葉を使用してメッセージに署名したら、それを破棄し、新しいLMSツリーを生成し、次の（レベルL-2）LMSツリーで署名します（そして、それが使い果たされると、再帰的に生成し、新しいレベルのL-2 LMSツリーに署名します）。
HSS, in essence, utilizes a tree of LMS trees. There is a single LMS tree at level 0 (the root). Each LMS tree (actually, the private key corresponding to the LMS tree) at level i is used to sign 2^h objects (where h is the height of trees at level i). If i < L-1, then each object will be another LMS tree (actually, the public key) at level i+1; if i = L-1, we've reached the bottom of the HSS tree, and so each object will be a message from the application. The HSS public key contains the public key of the LMS tree at the root, and an HSS signature is associated with a path from the root of the HSS tree to the leaf.
HSSは本質的に、LMSツリーのツリーを利用します。レベル0（ルート）に単一のLMSツリーがあります。レベルiの各LMSツリー（実際には、LMSツリーに対応する秘密鍵）を使用して、2 ^ hオブジェクト（hはレベルiのツリーの高さ）に署名します。 i <L-1の場合、各オブジェクトはレベルi + 1の別のLMSツリー（実際には公開鍵）になります。 i = L-1の場合、HSSツリーの最下部に達しているため、各オブジェクトはアプリケーションからのメッセージになります。 HSS公開鍵には、ルートにあるLMSツリーの公開鍵が含まれており、HSS署名は、HSSツリーのルートからリーフへのパスに関連付けられています。
Compared to LMS, HSS has a much reduced public key generation time, as only the root tree needs to be generated prior to the distribution of the HSS public key. For example, an L=3 tree (with h=10 at each level) would have one level 0 LMS tree, 2^10 level 1 LMS trees (with each such level 1 public key signed by one of the 1024 level 0 OTS public keys), and 2^20 level 2 LMS trees. Only 1024 OTS public keys need to be computed to generate the HSS public key (as you need to compute only the level 0 LMS tree to compute that value; you can, of course, decide to compute the initial level 1 and level 2 LMS trees). In addition, the 2^20 level 2 LMS trees can jointly sign a total of over a billion messages. In contrast, a single LMS tree that could sign a billion messages would require a billion OTS public keys to be computed first (if h=30 were allowed in a supported parameter set).
LSSと比較すると、HSS公開鍵の配布前にルートツリーのみを生成する必要があるため、HSSでは公開鍵生成時間が大幅に短縮されます。たとえば、L = 3ツリー（各レベルでh = 10の場合）には、1つのレベル0 LMSツリー、2 ^ 10レベル1 LMSツリー（1024などのレベル0のOTSのいずれかによって署名されたレベル1の公開鍵がそれぞれ1つずつあります）キー）、および2 ^ 20レベル2 LMSツリー。 HSS公開鍵を生成するために計算する必要があるのは1024のOTS公開鍵のみです（その値を計算するためにレベル0 LMSツリーのみを計算する必要があるため、もちろん、初期のレベル1およびレベル2 LMSツリーを計算することを決定できます） ）。さらに、2 ^ 20レベル2 LMSツリーは、合計10億を超えるメッセージに共同で署名できます。対照的に、10億のメッセージに署名できる単一のLMSツリーでは、10億のOTS公開鍵を最初に計算する必要があります（サポートされているパラメーターセットでh = 30が許可されている場合）。
Each LMS tree within the hierarchy is associated with a distinct LMS public key, private key, signature, and identifier. The number of levels is denoted as L and is between one and eight, inclusive. The following notation is used, where i is an integer between 0 and L-1 inclusive, and the root of the hierarchy is level 0:
階層内の各LMSツリーは、個別のLMS公開鍵、秘密鍵、署名、および識別子に関連付けられています。レベルの数はLで表され、1〜8の範囲です。次の表記法が使用されます。ここで、iは0からL-1までの整数で、階層のルートはレベル0です。
prv[i] is the current LMS private key of the i-th level.
prv [i]は、i番目のレベルの現在のLMS秘密鍵です。
pub[i] is the current LMS public key of the i-th level, as described in Section 5.3.
セクション5.3で説明されているように、pub [i]はi番目のレベルの現在のLMS公開鍵です。
sig[i] is the LMS signature of public key pub[i+1] generated using the private key prv[i].
sig [i]は、秘密鍵prv [i]を使用して生成された公開鍵pub [i + 1]のLMS署名です。
It is expected that the above arrays are maintained for the course of the HSS key. The contents of the prv[] array MUST be kept private; the pub[] and sig[] array may be revealed should the implementation find that convenient.
上記の配列は、HSSキーの過程で維持されることが期待されます。 prv []配列の内容は非公開にしておく必要があります。 pub []配列とsig []配列は、実装が便利だとわかった場合に明らかになる可能性があります。
In this section, we say that an N-time private key is exhausted when it has generated N signatures; thus, it can no longer be used for signing.
このセクションでは、N個の署名を生成したときにN回の秘密鍵が使い果たされたと言います。したがって、署名に使用することはできません。
For i > 0, the values prv[i], pub[i], and (for all values of i) sig[i] will be updated over time as private keys are exhausted and replaced by newer keys.
i> 0の場合、値prv [i]、pub [i]、および（iのすべての値の場合）sig [i]は、秘密鍵が使い果たされて新しいキーに置き換えられるため、時間の経過とともに更新されます。
When these key pairs are updated (or initially generated before the first message is signed), then the LMS key generation processes outlined in Sections 5.2 and 5.3 are performed. If the generated key pairs are for level i of the HSS hierarchy, then we store the public key in pub[i] and the private key in prv[i]. In addition, if i > 0, then we sign the generated public key with the LMS private key at level i-1, placing the signature into sig[i-1]. When the LMS key pair is generated, the key pair and the corresponding identifier MUST be generated independently of all other key pairs.
これらのキーペアが更新されると（または最初のメッセージが署名される前に最初に生成されると）、セクション5.2および5.3で説明されているLMSキー生成プロセスが実行されます。生成されたキーペアがHSS階層のレベルi用である場合、公開キーはpub [i]に、秘密キーはprv [i]に格納します。さらに、i> 0の場合、レベルi-1のLMS秘密鍵で生成された公開鍵に署名し、署名をsig [i-1]に配置します。 LMSキーペアが生成されるとき、キーペアと対応する識別子は、他のすべてのキーペアとは無関係に生成される必要があります。
HSS allows L=1, in which case the HSS public key and signature formats are essentially the LMS public key and signature formats, prepended by a fixed field. Since HSS with L=1 has very little overhead compared to LMS, all implementations MUST support HSS in order to maximize interoperability.
HSSはL = 1を許可します。この場合、HSS公開鍵と署名の形式は基本的にLMS公開鍵と署名の形式であり、先頭に固定フィールドが付加されます。 L = 1のHSSはLMSに比べてオーバーヘッドが非常に少ないため、相互運用性を最大化するために、すべての実装でHSSをサポートする必要があります。
We specifically allow different LMS levels to use different parameter sets. For example, the 0-th LMS public key (the root) may use the LMS_SHA256_M32_H15 parameter set, while the 1-th public key may use LMS_SHA256_M32_H10. There are practical reasons to allow this; for one, the signer may decide to store parts of the 0-th LMS tree (that it needs to construct while computing the public key) to accelerate later operations. As the 0-th tree is never updated, these internal nodes will never need to be recomputed. In addition, during the signature-generation operation, almost all the operations involved with updating the authentication path occur with the bottom (L-1th) LMS public key; hence, it may be useful to select the parameter set for that public key to have a shorter LMS tree.
特に、異なるLMSレベルで異なるパラメーターセットを使用することを許可します。たとえば、0番目のLMS公開鍵（ルート）はLMS_SHA256_M32_H15パラメータセットを使用でき、1番目の公開鍵はLMS_SHA256_M32_H10を使用できます。これを許可する実際的な理由があります。 1つは、署名者が後の操作を加速するために、0番目のLMSツリーの一部（公開鍵の計算中に構築する必要がある）を格納することを決定する場合があります。 0番目のツリーは更新されないため、これらの内部ノードを再計算する必要はありません。さらに、署名生成操作中、認証パスの更新に関連するほとんどすべての操作は、最下位（L-1番目）のLMS公開鍵で行われます。したがって、その公開鍵のパラメータセットを選択してLMSツリーを短くすると便利な場合があります。
A close reading of the HSS verification pseudocode shows that it would allow the parameters of the nontop LMS public keys to change over time; for example, the signer might initially have the 1-th LMS public key use the LMS_SHA256_M32_H10 parameter set, but when that tree is exhausted, the signer might replace it with an LMS public key that uses the LMS_SHA256_M32_H15 parameter set. While this would work with the example verification pseudocode, the signer MUST NOT change the parameter sets for a specific level. This prohibition is to support verifiers that may keep state over the course of several signature verifications.
HSS検証疑似コードをよく読むと、非上位のLMS公開鍵のパラメーターを時間の経過とともに変更できることがわかります。たとえば、署名者は最初に1番目のLMS公開鍵でLMS_SHA256_M32_H10パラメータセットを使用することがありますが、そのツリーが使い果たされると、署名者はそれをLMS_SHA256_M32_H15パラメータセットを使用するLMS公開鍵で置き換える場合があります。これはサンプルの検証疑似コードで機能しますが、署名者は特定のレベルのパラメーターセットを変更してはなりません。この禁止事項は、いくつかの署名検証の過程で状態を維持できる検証者をサポートすることです。
The public key of the HSS scheme consists of the number of levels L, followed by pub[0], the public key of the top level.
HSSスキームの公開鍵は、レベル数Lで構成され、その後に最上位レベルの公開鍵であるpub [0]が続きます。
The HSS private key consists of prv[0], ... , prv[L-1], along with the associated pub[0], ... pub[L-1] and sig[0], ..., sig[L-2] values. As stated earlier, the values of the pub[] and sig[] arrays need not be kept secret and may be revealed. The value of pub[0] does not change (and, except for the index q, the value of prv[0] need not change); however, the values of pub[i] and prv[i] are dynamic for i > 0 and are changed by the signature-generation algorithm.
HSS秘密鍵は、prv [0]、...、prv [L-1]と、関連するpub [0]、... pub [L-1]およびsig [0]、...、 sig [L-2]値。前述のように、pub []配列とsig []配列の値は秘密にしておく必要はなく、明らかにされる場合があります。 pub [0]の値は変化しません（インデックスqを除いて、prv [0]の値は変化する必要はありません）。ただし、pub [i]とprv [i]の値はi> 0の場合は動的であり、署名生成アルゴリズムによって変更されます。
During the key generation, the public and private keys are initialized. Here is some pseudocode that explains the key-generation logic:
鍵の生成中に、公開鍵と秘密鍵が初期化されます。以下は、キー生成ロジックを説明する擬似コードです。
Algorithm 7: Generating an HSS Key Pair
アルゴリズム7：HSS鍵ペアの生成
1. Generate an LMS key pair, as specified in Sections 5.2 and 5.3, placing the private key into priv[0], and the public key into pub[0]
1. セクション5.2と5.3で指定されているように、LMS鍵ペアを生成し、秘密鍵をpriv [0]に、公開鍵をpub [0]に配置します。
2. For i = 1 to L-1 do { generate an LMS key pair, placing the private key into priv[i] and the public key into pub[i]
2. i = 1からL-1の場合、{LMS鍵ペアを生成し、秘密鍵をpriv [i]に、公開鍵をpub [i]に配置します。
sig[i-1] = lms_signature( pub[i], priv[i-1] ) }
sig [i-1] = lms_signature（pub [i]、priv [i-1]）}
3. Return u32str(L) || pub[0] as the public key and the priv[], pub[], and sig[] arrays as the private key
3. u32str（L）を返す||公開鍵としてのpub [0]および秘密鍵としてのpriv []、pub []、およびsig []配列
In the above algorithm, each LMS public/private key pair generated MUST be generated independently.
上記のアルゴリズムでは、生成された各LMS公開/秘密鍵のペアは個別に生成する必要があります。
Note that the value of the public key does not depend on the execution of step 2. As a result, an implementation may decide to delay step 2 until later -- for example, during the initial signature-generation operation.
公開鍵の値はステップ2の実行に依存しないことに注意してください。その結果、実装は、たとえば最初の署名生成操作の間など、後でステップ2を遅らせることを決定する場合があります。
To sign a message using an HSS key pair, the following steps are performed:
HSSキーペアを使用してメッセージに署名するには、次の手順を実行します。
If prv[L-1] is exhausted, then determine the smallest integer d such that all of the private keys prv[d], prv[d+1], ... , prv[L-1] are exhausted. If d is equal to zero, then the HSS key pair is exhausted, and it MUST NOT generate any more signatures. Otherwise, the key pairs for levels d through L-1 must be regenerated during the signature-generation process, as follows. For i from d to L-1, a new LMS public and private key pair with a new identifier is generated, pub[i] and prv[i] are set to those values, then the public key pub[i] is signed with prv[i-1], and sig[i-1] is set to the resulting value.
prv [L-1]が使い果たされた場合、すべての秘密鍵prv [d]、prv [d + 1]、...、prv [L-1]が使い果たされるように、最小の整数dを決定します。 dがゼロに等しい場合、HSS鍵ペアは使い果たされており、それ以上署名を生成してはならない（MUST NOT）。それ以外の場合は、レベルd〜L-1のキーペアは、次のように、署名生成プロセス中に再生成する必要があります。 dからL-1までのiの場合、新しい識別子を持つ新しいLMS公開鍵と秘密鍵のペアが生成され、pub [i]とprv [i]がそれらの値に設定されてから、公開鍵pub [i]がprv [i-1]、およびsig [i-1]は結果の値に設定されます。
The message is signed with prv[L-1], and the value sig[L-1] is set to that result.
メッセージはprv [L-1]で署名され、値sig [L-1]がその結果に設定されます。
The value of the HSS signature is set as follows. We let signed_pub_key denote an array of octet strings, where signed_pub_key[i] = sig[i] || pub[i+1], for i between 0 and Nspk-1, inclusive, where Nspk = L-1 denotes the number of signed public keys. Then the HSS signature is u32str(Nspk) || signed_pub_key[0] || ... || signed_pub_key[Nspk-1] || sig[Nspk].
HSS署名の値は次のように設定されます。 signed_pub_keyにオクテット文字列の配列を示します。signed_pub_key[i] = sig [i] || pub [i + 1]、iが0からNspk-1までの場合、Nspk = L-1は署名された公開鍵の数を示します。次に、HSS署名はu32str（Nspk）です|| signed_pub_key [0] || ... || signed_pub_key [Nspk-1] || sig [Nspk]。
Note that the number of signed_pub_key elements in the signature is indicated by the value Nspk that appears in the initial four bytes of the signature.
署名のsigned_pub_key要素の数は、署名の最初の4バイトに表示される値Nspkによって示されることに注意してください。
Here is some pseudocode of the above logic:
上記のロジックの疑似コードを次に示します。
Algorithm 8: Generating an HSS signature
アルゴリズム8：HSS署名の生成
1. If the message-signing key prv[L-1] is exhausted, regenerate that key pair, together with any parent key pairs that might be necessary.
1. メッセージ署名鍵prv [L-1]を使い果たした場合は、必要になる可能性のある親鍵のペアとともに、その鍵のペアを再生成します。
If the root key pair is exhausted, then the HSS key pair is exhausted and MUST NOT generate any more signatures.
ルートキーペアが使い果たされると、HSSキーペアが使い果たされ、それ以上の署名を生成してはなりません（MUST NOT）。
d = L
while (prv[d-1].q == 2^(prv[d-1].h)) {
d = d - 1
if (d == 0)
return FAILURE
}
while (d < L) {
create lms key pair pub[d], prv[d]
sig[d-1] = lms_signature( pub[d], prv[d-1] )
d = d + 1
}
2. Sign the message. sig[L-1] = lms_signature( msg, prv[L-1] )
2. メッセージに署名します。 sig [L-1] = lms_signature（msg、prv [L-1]）
3. Create the list of signed public keys. i = 0; while (i < L-1) { signed_pub_key[i] = sig[i] || pub[i+1] i = i + 1 }
3. 署名済み公開鍵のリストを作成します。 i = 0; while（i <L-1）{signed_pub_key [i] = sig [i] || pub [i + 1] i = i + 1}
4. Return u32str(L-1) || signed_pub_key[0] || ... || signed_pub_key[L-2] || sig[L-1]
4. u32str（L-1）を返す|| signed_pub_key [0] || ... || signed_pub_key [L-2] || sig [L-1]
In the specific case of L=1, the format of an HSS signature is
L = 1の特定のケースでは、HSS署名の形式は次のとおりです。
u32str(0) || sig[0]
u32str（0）||外[0]
In the general case, the format of an HSS signature is
一般的な場合、HSS署名の形式は次のとおりです。
u32str(Nspk) || signed_pub_key[0] || ... || signed_pub_key[Nspk-1] || sig[Nspk]
u32str（Nspk）|| signed_pub_key [0] || ... || signed_pub_key [Nspk-1] || sig [Nspk]
which is equivalent to
これは
u32str(Nspk) || sig[0] || pub[1] || ... || sig[Nspk-1] || pub[Nspk] || sig[Nspk]
u32str（Nspk）|| sig [0] ||パブ[1] || ... || sig [Nspk-1] ||パブ[Nspk] ||見つかった[Nspk]
To verify a signature S and message using the public key pub, perform the following steps:
公開鍵pubを使用して署名Sおよびメッセージを検証するには、次の手順を実行します。
The signature S is parsed into its components as follows:
署名Sは、次のように構文解析されてそのコンポーネントになります。
Nspk = strTou32(first four bytes of S)
if Nspk+1 is not equal to the number of levels L in pub:
return INVALID
for (i = 0; i < Nspk; i = i + 1) {
siglist[i] = next LMS signature parsed from S
publist[i] = next LMS public key parsed from S
}
siglist[Nspk] = next LMS signature parsed from S
key = pub
for (i = 0; i < Nspk; i = i + 1) {
sig = siglist[i]
msg = publist[i]
if (lms_verify(msg, key, sig) != VALID):
return INVALID
key = msg
}
return lms_verify(message, key, siglist[Nspk])
Since the length of an LMS signature cannot be known without parsing it, the HSS signature verification algorithm makes use of an LMS signature parsing routine that takes as input a string consisting of an LMS signature with an arbitrary string appended to it and returns both the LMS signature and the appended string. The latter is passed on for further processing.
LMSシグニチャの長さは、それを解析しないとわからないため、HSSシグニチャ検証アルゴリズムでは、LMSシグニチャの解析ルーチンを使用して、任意の文字列が追加されたLMSシグニチャで構成される文字列を入力として受け取り、両方のLMSを返します。署名と追加された文字列。後者は、さらに処理するために渡されます。
As for guidance as to the number of LMS levels and the size of each, any discussion of performance is implementation specific. In general, the sole drawback for a single LMS tree is the time it takes to generate the public key; as every LM-OTS public key needs to be generated, the time this takes can be substantial. For a two-level tree, only the top-level LMS tree and the initial bottom-level LMS tree need to be generated initially (before the first signature is generated); this will in general be significantly quicker.
LMSレベルの数と各レベルのサイズに関するガイダンスについては、パフォーマンスの説明は実装固有です。一般に、単一のLMSツリーの唯一の欠点は、公開鍵の生成にかかる時間です。すべてのLM-OTS公開鍵を生成する必要があるため、これにはかなりの時間がかかる場合があります。 2レベルのツリーの場合、最初に（最初の署名が生成される前に）トップレベルのLMSツリーと最初のボトムレベルのLMSツリーのみを生成する必要があります。これは一般的にかなり速くなります。
To give a general idea of the trade-offs available, we include some measurements taken with the LMS implementation available at <https://github.com/cisco/hash-sigs>, taken on a 3.3 GHz Xeon processor with threading enabled. We tried various parameter sets, all with W=8 (which minimizes signature size, while increasing time). These are here to give a guideline as to what's possible; for the computational time, your mileage may vary, depending on the computing resources you have. The machine these tests were performed on does not have the SHA-256 extensions; you could possibly do significantly better.
利用可能なトレードオフの一般的なアイデアを提供するために、スレッド化を有効にした3.3 GHz Xeonプロセッサーで行われた、<https://github.com/cisco/hash-sigs>で利用可能なLMS実装で行われたいくつかの測定を含めます。さまざまなパラメーターセットを試してみましたが、すべてW = 8でした（これにより、時間を増やしながら、署名サイズを最小化しました）。これらは、可能なことについてのガイドラインを提供するためにここにあります。計算時間については、使用しているコンピューティングリソースに応じて、走行距離が異なる場合があります。これらのテストが実行されたマシンには、SHA-256拡張機能がありません。あなたはおそらくかなり良くすることができます。
+---------+------------+---------+-------------+
| ParmSet | KeyGenTime | SigSize | KeyLifetime |
+---------+------------+---------+-------------+
| 15 | 6 sec | 1616 | 30 seconds |
| | | | |
| 20 | 3 min | 1776 | 16 minutes |
| | | | |
| 25 | 1.5 hour | 1936 | 9 hours |
| | | | |
| 15/10 | 6 sec | 3172 | 9 hours |
| | | | |
| 15/15 | 6 sec | 3332 | 12 days |
| | | | |
| 20/10 | 3 min | 3332 | 12 days |
| | | | |
| 20/15 | 3 min | 3492 | 1 year |
| | | | |
| 25/10 | 1.5 hour | 3492 | 1 year |
| | | | |
| 25/15 | 1.5 hour | 3652 | 34 years |
+---------+------------+---------+-------------+
Table 3
表3
ParmSet: this is the height of the Merkle tree(s); parameter sets listed as a single integer have L=1 and consist of a single Merkle tree of that height; parameter sets with L=2 are listed as x/y, with x being the height of the top-level Merkle tree and y being the bottom level.
ParmSet：これはマークルツリーの高さです。単一の整数としてリストされているパラメーターセットはL = 1で、その高さの単一のマークルツリーで構成されています。 L = 2のパラメーターセットはx / yとしてリストされ、xは最上位のマークルツリーの高さ、yは最下位のレベルです。
KeyGenTime: the measured key-generation time; that is, the time needed to generate the public/private key pair.
KeyGenTime：測定された鍵生成時間。つまり、公開鍵と秘密鍵のペアの生成に必要な時間です。
SigSize: the size of a signature (in bytes)
SigSize：署名のサイズ（バイト単位）
KeyLifetime: the lifetime of a key, assuming we generated 1000 signatures per second. In practice, we're not likely to get anywhere close to 1000 signatures per second sustained; if you have a more appropriate figure for your scenario, this column is easy to recompute.
KeyLifetime：1秒あたり1000個の署名を生成したと仮定した場合の鍵の有効期間。実際には、1秒あたり1000の署名が維持される可能性はほとんどありません。シナリオに適した数値がある場合、この列は簡単に再計算できます。
As for signature generation or verification times, those are moderately insensitive to the above parameter settings (except for the Winternitz setting and the number of Merkle trees for verification). Tests on the same machine (without multithreading) gave approximately 4 msec to sign a short message, 2.6 msec to verify; these tests used a two-level ParmSet; a single level would approximately halve the verification time. All times can be significantly improved (by perhaps a factor of 8) by using a parameter set with W=4; however, that also about doubles the signature size.
署名の生成または検証時間に関しては、これらは上記のパラメーター設定の影響を受けません（Winternitz設定と検証用のマークルツリーの数を除く）。同じマシンでのテスト（マルチスレッドなし）では、短いメッセージに署名するために約4ミリ秒、確認するために2.6ミリ秒を与えました。これらのテストでは、2レベルのParmSetを使用しました。単一のレベルでは、検証時間が約半分になります。 W = 4のパラメーターセットを使用すると、すべての時間を大幅に改善できます（おそらく8倍にすることができます）。ただし、これにより署名サイズが約2倍になります。
The goal of this note is to describe the LM-OTS, LMS, and HSS algorithms following the original references and present the modern security analysis of those algorithms. Other signature methods are out of scope and may be interesting follow-on work.
このノートの目的は、元のリファレンスに従ってLM-OTS、LMS、およびHSSアルゴリズムを説明し、これらのアルゴリズムの最新のセキュリティ分析を提示することです。他の署名方法は範囲外であり、興味深い後続作業になる可能性があります。
We adopt the techniques described by Leighton and Micali to mitigate attacks that amortize their work over multiple invocations of the hash function.
LeightonとMicaliが説明した手法を採用して、ハッシュ関数の複数回の呼び出しで作業を償却する攻撃を軽減します。
The values taken by the identifier I across different LMS public/ private key pairs are chosen randomly in order to improve security. The analysis of this method in [Fluhrer17] shows that we do not need uniqueness to ensure security; we do need to ensure that we don't have a large number of private keys that use the same I value. By randomly selecting 16-byte I values, the chance that, out of 2^64 private keys, 4 or more of them will use the same I value is negligible (that is, has probability less than 2^-128).
セキュリティを向上させるために、LMSの公開鍵と秘密鍵のペア全体で識別子Iが取得する値は、ランダムに選択されます。 [Fluhrer17]でのこのメソッドの分析は、セキュリティを確保するために一意性を必要としないことを示しています。同じI値を使用する秘密鍵が多数ないようにする必要があります。 16バイトのI値をランダムに選択することにより、2 ^ 64個の秘密鍵のうち、4個以上が同じI値を使用する可能性は無視できます（つまり、確率は2 ^ -128未満です）。
The reason 16-byte I values were selected was to optimize the Winternitz hash-chain operation. With the current settings, the value being hashed is exactly 55 bytes long (for a 32-byte hash function), which SHA-256 can hash in a single hash-compression operation. Other hash functions may be used in future specifications; all the ones that we will be likely to support (SHA-512/256 and the various SHA-3 hashes) would work well with a 16-byte I value.
16バイトのI値が選択された理由は、Winternitzハッシュチェーン操作を最適化するためです。現在の設定では、ハッシュされる値は正確に55バイト長（32バイトのハッシュ関数の場合）であり、SHA-256は単一のハッシュ圧縮操作でハッシュできます。その他のハッシュ関数は、将来の仕様で使用される可能性があります。私たちがサポートする可能性が高いすべてのもの（SHA-512 / 256およびさまざまなSHA-3ハッシュ）は、16バイトのI値でうまく機能します。
The signature and public key formats are designed so that they are relatively easy to parse. Each format starts with a 32-bit enumeration value that indicates the details of the signature algorithm and provides all of the information that is needed in order to parse the format.
署名と公開鍵の形式は、比較的簡単に解析できるように設計されています。各形式は、署名アルゴリズムの詳細を示す32ビットの列挙値で始まり、形式を解析するために必要なすべての情報を提供します。
The Checksum (Section 4.4) is calculated using a nonnegative integer
"sum" whose width was chosen to be an integer number of w-bit fields
such that it is capable of holding the difference of the total
possible number of applications of the function H (as defined in the
signing algorithm of Section 4.5) and the total actual number. In
the case that the number of times H is applied is 0, the sum is (2^w
- 1) * (8*n/w). Thus, for the purposes of this document, which
describes signature methods based on H = SHA256 (n = 32 bytes) and w
= { 1, 2, 4, 8 }, the sum variable is a 16-bit nonnegative integer
for all combinations of n and w. The calculation uses the parameter
ls defined in Section 4.1 and calculated in Appendix B, which
indicates the number of bits used in the left-shift operation.
To improve security against attacks that amortize their effort against multiple invocations of the hash function, Leighton and Micali introduced a "security string" that is distinct for each invocation of that function. Whenever this process computes a hash, the string being hashed will start with a string formed from the fields below. These fields will appear in fixed locations in the value we compute the hash of, and so we list where in the hash these fields would be present. The fields that make up this string are as follows:
ハッシュ関数の複数の呼び出しに対する攻撃を償却する攻撃に対するセキュリティを強化するために、レイトンとミカリは、その関数の呼び出しごとに異なる「セキュリティ文字列」を導入しました。このプロセスがハッシュを計算するときはいつでも、ハッシュされる文字列は、以下のフィールドから形成された文字列で始まります。これらのフィールドは、ハッシュを計算する値の固定位置に表示されるため、これらのフィールドが存在するハッシュの場所をリストします。この文字列を構成するフィールドは次のとおりです。
I A 16-byte identifier for the LMS public/private key pair. It MUST be chosen uniformly at random, or via a pseudorandom process, at the time that a key pair is generated, in order to minimize the probability that any specific value of I be used for a large number of different LMS private keys. This is always bytes 0-15 of the value being hashed.
I LMS公開/秘密鍵ペアの16バイトの識別子。多数の異なるLMS秘密キーに特定の値が使用される可能性を最小限に抑えるために、キーペアが生成されるときに、ランダムに、または疑似ランダムプロセスを介して均一に選択する必要があります。これは常に、ハッシュされる値のバイト0〜15です。
r In the LMS N-time signature scheme, the node number r associated with a particular node of a hash tree is used as an input to the hash used to compute that node. This value is represented as a 32-bit (four byte) unsigned integer in network byte order. Either r or q (depending on the domain-separation parameter) will be bytes 16-19 of the value being hashed.
r LMSのN時間署名方式では、ハッシュツリーの特定のノードに関連付けられているノード番号rが、そのノードの計算に使用されるハッシュへの入力として使用されます。この値は、ネットワークバイトオーダーの32ビット（4バイト）の符号なし整数として表されます。 rまたはq（ドメイン分離パラメーターに応じて）は、ハッシュされる値のバイト16〜19になります。
q In the LMS N-time signature scheme, each LM-OTS signature is associated with the leaf of a hash tree, and q is set to the leaf number. This ensures that a distinct value of q is used for each distinct LM-OTS public/private key pair. This value is represented as a 32-bit (four byte) unsigned integer in network byte order. Either r or q (depending on the domain-separation parameter) will be bytes 16-19 of the value being hashed.
q LMS N-time署名スキームでは、各LM-OTS署名はハッシュツリーのリーフに関連付けられ、qはリーフ番号に設定されます。これにより、個別のLM-OTS公開/秘密鍵ペアごとに個別の値qが使用されることが保証されます。この値は、ネットワークバイトオーダーの32ビット（4バイト）の符号なし整数として表されます。 rまたはq（ドメイン分離パラメーターに応じて）は、ハッシュされる値のバイト16〜19になります。
D A domain-separation parameter, which is a two-byte identifier that takes on different values in the different contexts in which the hash function is invoked. D occurs in bytes 20 and 21 of the value being hashed and takes on the following values:
Dドメイン分離パラメーター。これは、ハッシュ関数が呼び出される異なるコンテキストで異なる値をとる2バイトのIDです。 Dは、ハッシュされる値のバイト20および21で発生し、次の値を取ります。
D_PBLC = 0x8080 when computing the hash of all of the iterates in the LM-OTS algorithm
LM-OTSアルゴリズムですべての反復のハッシュを計算する場合、D_PBLC = 0x8080
D_MESG = 0x8181 when computing the hash of the message in the LM-OTS algorithms
LM-OTSアルゴリズムでメッセージのハッシュを計算する場合、D_MESG = 0x8181
D_LEAF = 0x8282 when computing the hash of the leaf of an LMS tree
LMSツリーの葉のハッシュを計算する場合、D_LEAF = 0x8282
D_INTR = 0x8383 when computing the hash of an interior node of an LMS tree
LMSツリーの内部ノードのハッシュを計算する場合、D_INTR = 0x8383
i A value between 0 and 264; this is used in the LM-OTS scheme when either computing the iterations of the Winternitz chain or using the suggested LM-OTS private key generation process. It is represented as a 16-bit (two-byte) unsigned integer in network byte order. If present, it occurs at bytes 20 and 21 of the value being hashed.
i 0〜264の値。これは、Winternitzチェーンの反復を計算するとき、または提案されたLM-OTS秘密キー生成プロセスを使用するときに、LM-OTSスキームで使用されます。これは、ネットワークバイトオーダーの16ビット（2バイト）の符号なし整数として表されます。存在する場合、ハッシュされる値のバイト20および21で発生します。
j In the LM-OTS scheme, j is the iteration number used when the private key element is being iteratively hashed. It is represented as an 8-bit (one byte) unsigned integer and is present if i is a value between 0 and 264. If present, it occurs at bytes 22 to 21+n of the value being hashed.
j LM-OTSスキームでは、jは秘密鍵要素が繰り返しハッシュされるときに使用される反復数です。これは、8ビット（1バイト）の符号なし整数として表され、iが0から264までの値の場合に存在します。存在する場合は、ハッシュされる値のバイト22から21 + nで発生します。
C An n-byte randomizer that is included with the message whenever it is being hashed to improve security. C MUST be chosen uniformly at random or via another unpredictable process. It is present if D=D_MESG, and it occurs at bytes 22 to 21+n of the value being hashed.
Cセキュリティを向上させるためにメッセージがハッシュされるたびにメッセージに含まれるnバイトのランダマイザー。 Cはランダムに、または別の予測不可能なプロセスを介して均一に選択する必要があります。 D = D_MESGの場合に存在し、ハッシュされる値のバイト22〜21 + nで発生します。
IANA has created two registries: "LM-OTS Signatures", which includes all of the LM-OTS signatures as defined in Section 4, and "Leighton-Micali Signatures (LMS)" for LMS as defined in Section 5.
IANAは2つのレジストリを作成しました。セクション4で定義されているすべてのLM-OTSシグネチャを含む「LM-OTSシグネチャ」とセクション5で定義されているLMSの「Leighton-Micali Signatures（LMS）」です。
Additions to these registries require that a specification be documented in an RFC or another permanent and readily available reference in sufficient detail that interoperability between independent implementations is possible [RFC8126]. IANA MUST verify that all applications for additions to these registries have first been reviewed by the IRTF Crypto Forum Research Group (CFRG).
これらのレジストリへの追加は、仕様がRFCまたは別の永続的で容易に入手可能なリファレンスで十分に詳細に文書化され、独立した実装間の相互運用が可能であることを要求します[RFC8126]。 IANAは、これらのレジストリへの追加のすべての申請が、IRTF暗号フォーラム研究グループ（CFRG）によって最初にレビューされていることを確認する必要があります。
Each entry in either of the registries contains the following elements:
いずれかのレジストリの各エントリには、次の要素が含まれています。
a short name (Name), such as "LMS_SHA256_M32_H10",
「LMS_SHA256_M32_H10」などの短い名前（名前）、
a positive number (Numeric Identifier), and
正の数（数値識別子）、および
a Reference to a specification that completely defines the signature-method test cases that can be used to verify the correctness of an implementation.
実装の正確性を検証するために使用できる署名方法のテストケースを完全に定義する仕様への参照。
The numbers between 0xDDDDDDDD (decimal 3,722,304,989) and 0xFFFFFFFF (decimal 4,294,967,295), inclusive, will not be assigned by IANA and are reserved for private use; no attempt will be made to prevent multiple sites from using the same value in different (and incompatible) ways [RFC8126].
0xDDDDDDDD（10進数の3,722,304,989）と0xFFFFFFFF（10進数の4,294,967,295）の間の数値は、IANAによって割り当てられず、私用に予約されています。複数のサイトが異なる（互換性のない）方法で同じ値を使用することを防ぐ試みは行われません[RFC8126]。
The initial contents of the "LM-OTS Signatures" registry are as follows.
「LM-OTS Signatures」レジストリの初期内容は以下の通りです。
+--------------------------+-----------+--------------------------+
| Name | Reference | Numeric Identifier |
+--------------------------+-----------+--------------------------+
| Reserved | | 0x00000000 |
| | | |
| LMOTS_SHA256_N32_W1 | Section 4 | 0x00000001 |
| | | |
| LMOTS_SHA256_N32_W2 | Section 4 | 0x00000002 |
| | | |
| LMOTS_SHA256_N32_W4 | Section 4 | 0x00000003 |
| | | |
| LMOTS_SHA256_N32_W8 | Section 4 | 0x00000004 |
| | | |
| Unassigned | | 0x00000005 - 0xDDDDDDDC |
| | | |
| Reserved for Private Use | | 0xDDDDDDDD - 0xFFFFFFFF |
+--------------------------+-----------+--------------------------+
Table 4
表4
The initial contents of the "Leighton Micali Signatures (LMS)" registry are as follows.
「Leighton Micali Signatures（LMS）」レジストリの初期内容は次のとおりです。
+--------------------------+-----------+--------------------------+
| Name | Reference | Numeric Identifier |
+--------------------------+-----------+--------------------------+
| Reserved | | 0x0 - 0x4 |
| | | |
| LMS_SHA256_M32_H5 | Section 5 | 0x00000005 |
| | | |
| LMS_SHA256_M32_H10 | Section 5 | 0x00000006 |
| | | |
| LMS_SHA256_M32_H15 | Section 5 | 0x00000007 |
| | | |
| LMS_SHA256_M32_H20 | Section 5 | 0x00000008 |
| | | |
| LMS_SHA256_M32_H25 | Section 5 | 0x00000009 |
| | | |
| Unassigned | | 0x0000000A - 0xDDDDDDDC |
| | | |
| Reserved for Private Use | | 0xDDDDDDDD - 0xFFFFFFFF |
+--------------------------+-----------+--------------------------+
Table 5
表5
An IANA registration of a signature system does not constitute an endorsement of that system or its security.
署名システムのIANA登録は、そのシステムまたはそのセキュリティの推奨を構成するものではありません。
Currently, the two registries assign a disjoint set of values to the defined parameter sets. This coincidence is a historical accident; the correctness of the system does not depend on this. IANA is not required to maintain this situation.
現在、2つのレジストリーは、定義されたパラメーター・セットに互いに素な値のセットを割り当てています。この偶然は歴史的な事故です。システムの正確さはこれに依存しません。 IANAはこの状況を維持する必要はありません。
The hash function H MUST have second preimage resistance: it must be computationally infeasible for an attacker that is given one message M to be able to find a second message M' such that H(M) = H(M').
ハッシュ関数Hは2番目のプリイメージ耐性を持たなければなりません。1つのメッセージMを与えられた攻撃者がH（M）= H（M '）のような2番目のメッセージM'を見つけられるようにすることは、計算上不可能でなければなりません。
The security goal of a signature system is to prevent forgeries. A successful forgery occurs when an attacker who does not know the private key associated with a public key can find a message (distinct from all previously signed ones) and signature that is valid with that public key (that is, the Signature Verification algorithm applied to that signature and message and public key will return VALID). Such an attacker, in the strongest case, may have the ability to forge valid signatures for an arbitrary number of other messages.
署名システムのセキュリティ目標は、偽造を防ぐことです。偽造が成功するのは、公開鍵に関連付けられた秘密鍵を知らない攻撃者が、メッセージ（以前に署名されたものとは異なる）とその公開鍵で有効な署名（つまり、その署名とメッセージおよび公開鍵はVALIDを返します）。そのような攻撃者は、最強の場合、他の任意の数のメッセージの有効な署名を偽造する可能性があります。
LMS is provably secure in the random oracle model, as shown by [Katz16]. In addition, further analysis is done by [Fluhrer17], where the hash compression function (rather than the entire hash function) is considered to be a random oracle. Corollary 1 of the latter paper states:
[Katz16]で示されているように、LMSはランダムオラクルモデルで証明できるほど安全です。さらに、[Fluhrer17]によってさらに分析が行われ、ハッシュ関数全体（ハッシュ関数全体ではなく）がランダムなオラクルであると見なされます。後者の論文の結果1は次のように述べています。
If we have no more than 2^64 randomly chosen LMS private keys, allow the attacker access to a signing oracle and a SHA-256 hash compression oracle, and allow a maximum of 2^120 hash compression computations, then the probability of an attacker being able to generate a single forgery against any of those LMS keys is less than 2^-129.
ランダムに選択されたLMS秘密鍵が2 ^ 64以下の場合、攻撃者が署名オラクルとSHA-256ハッシュ圧縮オラクルにアクセスできるようにし、最大2 ^ 120のハッシュ圧縮計算を許可してから、攻撃者の確率これらのLMSキーのいずれかに対して単一の偽造を生成できることは、2 ^ -129未満です。
Many of the objects within the public key and the signature start with a typecode. A verifier MUST check each of these typecodes, and a verification operation on a signature with an unknown type, or a type that does not correspond to the type within the public key, MUST return INVALID. The expected length of a variable-length object can be determined from its typecode; if an object has a different length, then any signature computed from the object is INVALID.
公開鍵と署名内のオブジェクトの多くは、タイプコードで始まります。検証者はこれらの各タイプコードをチェックしなければならず、未知のタイプ、または公開鍵内のタイプに対応しないタイプの署名の検証操作は、INVALIDを返さなければなりません（MUST）。可変長オブジェクトの予想される長さは、そのタイプコードから決定できます。オブジェクトの長さが異なる場合、オブジェクトから計算された署名は無効です。
The format of the inputs to the hash function H has the property that each invocation of that function has an input that is repeated by a small bounded number of other inputs (due to potential repeats of the I value). In particular, it will vary somewhere in the first 23 bytes of the value being hashed. This property is important for a proof of security in the random oracle model.
ハッシュ関数Hへの入力の形式には、その関数の呼び出しごとに、（I値が繰り返される可能性があるため）限られた数の他の入力によって繰り返される入力があるという特性があります。特に、ハッシュされる値の最初の23バイトのどこかで異なります。この特性は、ランダムオラクルモデルでのセキュリティの証明に重要です。
The formats used during key generation and signing (including the recommended pseudorandom key-generation procedure in Appendix A) are as follows:
キーの生成と署名（付録Aの推奨擬似ランダムキー生成手順を含む）で使用される形式は次のとおりです。
I || u32str(q) || u16str(i) || u8str(j) || tmp
I || u32str(q) || u16str(D_PBLC) || y[0] || ... || y[p-1]
I || u32str(q) || u16str(D_MESG) || C || message
I || u32str(r) || u16str(D_LEAF) || OTS_PUB_HASH[r-2^h]
I || u32str(r) || u16str(D_INTR) || T[2*r] || T[2*r+1]
I || u32str(q) || u16str(i) || u8str(0xff) || SEED
Each hash type listed is distinct; at locations 20 and 21 of the value being hashed, there exists either a fixed value D_PBLC, D_MESG, D_LEAF, D_INTR, or a 16-bit value i. These fixed values are distinct from each other and are large (over 32768), while the 16-bit values of i are small (currently no more than 265; possibly being slightly larger if larger hash functions are supported); hence, the range of possible values of i will not collide any of the D_PBLC, D_MESG, D_LEAF, D_INTR identifiers. The only other collision possibility is the Winternitz chain hash colliding with the recommended pseudorandom key-generation process; here, at location 22 of the value being hashed, the Winternitz chain function has the value u8str(j), where j is a value between 0 and 254, while location 22 of the recommended pseudorandom key-generation process has value 255.
リストされているハッシュタイプはそれぞれ異なります。ハッシュされる値の位置20および21には、固定値D_PBLC、D_MESG、D_LEAF、D_INTR、または16ビット値iのいずれかが存在します。これらの固定値は互いに異なり、大きい（32768を超える）一方で、iの16ビット値は小さいです（現在は265以下です。より大きなハッシュ関数がサポートされている場合は少し大きい可能性があります）。したがって、可能なiの値の範囲は、D_PBLC、D_MESG、D_LEAF、D_INTR識別子のどれとも衝突しません。他の唯一の衝突の可能性は、推奨される疑似ランダムキー生成プロセスと衝突するWinternitzチェーンハッシュです。ここで、ハッシュされる値の位置22で、Winternitzチェーン関数は値u8str（j）を持ちます。jは0から254までの値ですが、推奨される擬似ランダムキー生成プロセスの位置22は値255です。
For the Winternitz chaining function, D_PBLC, and D_MESG, the value of I || u32str(q) is distinct for each LMS leaf (or equivalently, for each q value). For the Winternitz chaining function, the value of u16str(i) || u8str(j) is distinct for each invocation of H for a given leaf. For D_PBLC and D_MESG, the input format is used only once for each value of q and, thus, distinctness is assured. The formats for D_INTR and D_LEAF are used exactly once for each value of r, which ensures their distinctness. For the recommended pseudorandom key-generation process, for a given value of I, q and j are distinct for each invocation of H.
Winternitz連鎖関数、D_PBLC、およびD_MESGの場合、Iの値|| u32str（q）は、LMSリーフごとに（または同等に、q値ごとに）異なります。 Winternitz連鎖関数の場合、u16str（i）の値|| u8str（j）は、指定されたリーフに対するHの呼び出しごとに異なります。 D_PBLCおよびD_MESGの場合、入力フォーマットはqの値ごとに1回だけ使用されるため、区別が保証されます。 D_INTRとD_LEAFのフォーマットは、rの各値に対して1回だけ使用され、それらの区別が確実になります。推奨される疑似ランダムキー生成プロセスでは、Iの特定の値について、Hの呼び出しごとにqとjが異なります。
The value of I is chosen uniformly at random from the set of all 128-bit strings. If 2^64 public keys are generated (and, hence, 2^64 random I values), there is a nontrivial probability of a duplicate (which would imply duplicate prefixes). However, there will be an extremely high probability there will not be a four-way collision (that is, any I value used for four distinct LMS keys; probability < 2^-132), and, hence, the number of repeats for any specific prefix will be limited to at most three. This is shown (in [Fluhrer17]) to have only a limited effect on the security of the system.
Iの値は、すべての128ビット文字列のセットからランダムに一様に選択されます。 2 ^ 64個の公開鍵が生成されると（したがって、2 ^ 64個のランダムなI値が）、重複する可能性があります（プレフィックスの重複を意味します）。ただし、4方向の衝突が発生しない可能性が非常に高く（つまり、4つの異なるLMSキーに使用される任意のI値、確率<2 ^ -132）、したがって、任意の繰り返しの数特定のプレフィックスは最大3つに制限されます。これは（[Fluhrer17]で）システムのセキュリティに限られた影響しか及ぼさないことが示されています。
The LMS signature system, like all N-time signature systems, requires that the signer maintain state across different invocations of the signing algorithm to ensure that none of the component one-time signature systems are used more than once. This section calls out some important practical considerations around this statefulness. These issues are discussed in greater detail in [STMGMT].
LMS署名システムでは、すべてのN-time署名システムと同様に、署名者が署名アルゴリズムのさまざまな呼び出しにわたって状態を維持して、コンポーネントの1回限りの署名システムが2回以上使用されないようにする必要があります。このセクションでは、このステートフル性に関するいくつかの重要な実用的な考慮事項について説明します。これらの問題については、[STMGMT]で詳細に説明されています。
In a typical computing environment, a private key will be stored in nonvolatile media such as on a hard drive. Before it is used to sign a message, it will be read into an application's Random-Access Memory (RAM). After a signature is generated, the value of the private key will need to be updated by writing the new value of the private key into nonvolatile storage. It is essential for security that the application ensures that this value is actually written into that storage, yet there may be one or more memory caches between it and the application. Memory caching is commonly done in the file system and in a physical memory unit on the hard disk that is dedicated to that purpose. To ensure that the updated value is written to physical media, the application may need to take several special steps. In a POSIX environment, for instance, the O_SYNC flag (for the open() system call) will cause invocations of the write() system call to block the calling process until the data has been written to the underlying hardware. However, if that hardware has its own memory cache, it must be separately dealt with using an operating system or device-specific tool such as hdparm to flush the on-drive cache or turn off write caching for that drive. Because these details vary across different operating systems and devices, this note does not attempt to provide complete guidance; instead, we call the implementer's attention to these issues.
一般的なコンピューティング環境では、秘密鍵はハードドライブなどの不揮発性メディアに保存されます。メッセージの署名に使用される前に、メッセージはアプリケーションのランダムアクセスメモリ（RAM）に読み込まれます。署名が生成された後、秘密鍵の新しい値を不揮発性ストレージに書き込むことにより、秘密鍵の値を更新する必要があります。アプリケーションがこの値が実際にそのストレージに書き込まれることを保証することはセキュリティにとって不可欠ですが、それとアプリケーションの間に1つ以上のメモリキャッシュが存在する場合があります。メモリキャッシングは通常、ファイルシステムと、その目的専用のハードディスク上の物理メモリユニットで行われます。更新された値が確実に物理メディアに書き込まれるようにするには、アプリケーションでいくつかの特別な手順を実行する必要がある場合があります。たとえば、POSIX環境では、O_SYNCフラグ（open()システムコール用）により、データが基盤となるハードウェアに書き込まれるまで、write()システムコールが呼び出され、呼び出しプロセスがブロックされます。ただし、そのハードウェアに独自のメモリキャッシュがある場合は、オペレーティングシステムまたはhdparmなどのデバイス固有のツールを使用して、ドライブ上のキャッシュをフラッシュするか、そのドライブの書き込みキャッシュをオフにする必要があります。これらの詳細はオペレーティングシステムやデバイスによって異なるため、このノートでは完全なガイダンスを提供することを試みていません。代わりに、これらの問題に対する実装者の注意を呼びかけます。
When hierarchical signatures are used, an easy way to minimize the private key synchronization issues is to have the private key for the second-level resident in RAM only and never write that value into nonvolatile memory. A new second-level public/private key pair will be generated whenever the application (re)starts; thus, failures such as a power outage or application crash are automatically accommodated. Implementations SHOULD use this approach wherever possible.
階層型署名を使用する場合、秘密鍵の同期の問題を最小限に抑える簡単な方法は、第2レベルの秘密鍵をRAMにのみ常駐させ、その値を不揮発性メモリに書き込まないことです。アプリケーションが（再）起動すると、新しい第2レベルの公開/秘密鍵のペアが生成されます。したがって、停電やアプリケーションのクラッシュなどの障害に自動的に対応します。実装では、可能な限りこのアプローチを使用する必要があります。
To show the security of LM-OTS checksum, we consider the signature y of a message with a private key x and let h = H(message) and c = Cksm(H(message)) (see Section 4.5). To attempt a forgery, an attacker may try to change the values of h and c. Let h' and c' denote the values used in the forgery attempt. If for some integer j in the range 0 to u, where u = ceil(8*n/w) is the size of the range that the checksum value can cover, inclusive,
LM-OTSチェックサムのセキュリティを示すために、秘密鍵xを持つメッセージの署名yを考慮し、h = H（メッセージ）およびc = Cksm（H（メッセージ））とします（セクション4.5を参照）。偽造を試みるために、攻撃者はhとcの値を変更しようとする可能性があります。 h 'とc'が偽造の試みで使用された値を示すとします。 0からuの範囲の整数jの場合、u = ceil（8 * n / w）は、チェックサム値がカバーできる範囲のサイズです。
a' = coef(h', j, w),
a '= coef（h'、j、w）、
a = coef(h, j, w), and
a = coef（h、j、w）、および
a' > a
a '> a
then the attacker can compute F^a'(x[j]) from F^a(x[j]) = y[j] by iteratively applying function F to the j-th term of the signature an additional (a' - a) times. However, as a result of the increased number of hashing iterations, the checksum value c' will decrease from its original value of c. Thus, a valid signature's checksum will have, for some number k in the range u to (p-1), inclusive,
次に、攻撃者は、関数Fを署名のj番目の項に繰り返し適用することにより、F ^ a（x [j]）= y [j]からF ^ a '（x [j]）を計算できます（a'- a）回。ただし、ハッシュの反復回数が増加した結果、チェックサム値c 'は元の値cから減少します。したがって、有効な署名のチェックサムは、uから（p-1）までの範囲のいくつかの数kに対して、
b' = coef(c', k, w),
b '= coef（c'、k、w）、
b = coef(c, k, w), and
b = coef（c、k、w）、および
b' < b
b '<b
Due to the one-way property of F, the attacker cannot easily compute F^b'(x[k]) from F^b(x[k]) = y[k].
Fには一方向のプロパティがあるため、攻撃者はF ^ b（x [k]）= y [k]からF ^ b '（x [k]）を簡単に計算できません。
The eXtended Merkle Signature Scheme (XMSS) is similar to HSS in several ways [XMSS][RFC8391]. Both are stateful hash-based signature schemes, and both use a hierarchical approach, with a Merkle tree at each level of the hierarchy. XMSS signatures are slightly shorter than HSS signatures, for equivalent security and an equal number of signatures.
拡張マークル署名スキーム（XMSS）は、いくつかの点で[XMSS] [RFC8391]でHSSに似ています。どちらもハッシュベースのステートフル署名方式であり、階層の各レベルにマークルツリーを使用した階層アプローチを使用しています。 XMSS署名は、同等のセキュリティと同じ数の署名のために、HSS署名よりもわずかに短いです。
HSS has several advantages over XMSS. HSS operations are roughly four times faster than the comparable XMSS ones, when SHA256 is used as the underlying hash. This occurs because the hash operation done as a part of the Winternitz iterations dominates performance, and XMSS performs four compression-function invocations (two for the PRF, two for the F function) where HSS only needs to perform one. Additionally, HSS is somewhat simpler (as each hash invocation is just a prefix followed by the data being hashed).
HSSには、XMSSに比べていくつかの利点があります。 SHA256が基礎となるハッシュとして使用される場合、HSS操作は、同等のXMSS操作よりも約4倍高速です。これは、Winternitz反復の一部として行われるハッシュ操作がパフォーマンスを支配し、XMSSが4つの圧縮関数呼び出しを実行するため（2つはPRF用、2つはF関数用）、HSSは1つだけ実行する必要があるためです。さらに、HSSは多少単純です（各ハッシュ呼び出しは、接頭辞の後にハッシュされるデータが続くだけなので）。
[FIPS180] National Institute of Standards and Technology, "Secure Hash Standard (SHS)", FIPS PUB 180-4, DOI 10.6028/NIST.FIPS.180-4, March 2012.
[FIPS180]米国国立標準技術研究所、「Secure Hash Standard（SHS）」、FIPS PUB 180-4、DOI 10.6028 / NIST.FIPS.180-4、2012年3月。
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, <https://www.rfc-editor.org/info/rfc2119>.
[RFC2119] Bradner、S。、「要件レベルを示すためにRFCで使用するキーワード」、BCP 14、RFC 2119、DOI 10.17487 / RFC2119、1997年3月、<https://www.rfc-editor.org/info/ rfc2119>。
[RFC4506] Eisler, M., Ed., "XDR: External Data Representation Standard", STD 67, RFC 4506, DOI 10.17487/RFC4506, May 2006, <https://www.rfc-editor.org/info/rfc4506>.
[RFC4506] Eisler、M。、編、「XDR：外部データ表現標準」、STD 67、RFC 4506、DOI 10.17487 / RFC4506、2006年5月、<https://www.rfc-editor.org/info/rfc4506 >。
[RFC8126] Cotton, M., Leiba, B., and T. Narten, "Guidelines for Writing an IANA Considerations Section in RFCs", BCP 26, RFC 8126, DOI 10.17487/RFC8126, June 2017, <https://www.rfc-editor.org/info/rfc8126>.
[RFC8126]コットン、M。、レイバ、B。、およびT.ナルテン、「RFCでIANAの考慮事項セクションを作成するためのガイドライン」、BCP 26、RFC 8126、DOI 10.17487 / RFC8126、2017年6月、<https：// www .rfc-editor.org / info / rfc8126>。
[RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, May 2017, <https://www.rfc-editor.org/info/rfc8174>.
[RFC8174] Leiba、B。、「RFC 2119キーワードの大文字と小文字のあいまいさ」、BCP 14、RFC 8174、DOI 10.17487 / RFC8174、2017年5月、<https://www.rfc-editor.org/info/ rfc8174>。
[RFC8179] Bradner, S. and J. Contreras, "Intellectual Property Rights in IETF Technology", BCP 79, RFC 8179, DOI 10.17487/RFC8179, May 2017, <https://www.rfc-editor.org/info/rfc8179>.
[RFC8179] Bradner、S。およびJ. Contreras、「IETFテクノロジーの知的財産権」、BCP 79、RFC 8179、DOI 10.17487 / RFC8179、2017年5月、<https://www.rfc-editor.org/info/ rfc8179>。
[USPTO5432852] Leighton, T. and S. Micali, "Large provably fast and secure digital signature schemes based on secure hash functions", U.S. Patent 5,432,852, July 1995.
[USPTO5432852] Leighton、T.およびS. Micali、「安全なハッシュ関数に基づく、大きくて高速かつ安全なデジタル署名方式」、米国特許第5,432,852、1995年7月。
[C:Merkle87] Merkle, R., "A Digital Signature Based on a Conventional Encryption Function", in Advances in Cryptology -- CRYPTO '87 Proceedings, Lecture Notes in Computer Science Vol. 293, DOI 10.1007/3-540-48184-2_32, 1988.
[C：Merkle87]暗号学の進歩におけるMerkle、R。、「従来の暗号化関数に基づくデジタル署名」-CRYPTO '87 Proceedings、Lecture Notes in Computer Science Vol。 293、DOI 10.1007 / 3-540-48184-2_32、1988。
[C:Merkle89a] Merkle, R., "A Certified Digital Signature", in Advances in Cryptology -- CRYPTO '89 Proceedings, Lecture Notes in Computer Science Vol. 435, DOI 10.1007/0-387-34805-0_21, 1990.
[C：Merkle89a] Merkle、R。、「A Certified Digital Signature」、Advance in Cryptology-CRYPTO '89 Proceedings、Lecture Notes in Computer Science Vol。 435、DOI 10.1007 / 0-387-34805-0_21、1990。
[C:Merkle89b] Merkle, R., "One Way Hash Functions and DES", in Advances in Cryptology -- CRYPTO '89 Proceedings, Lecture Notes in Computer Science Vol. 435, DOI 10.1007/0-387-34805-0_40, 1990.
[C：Merkle89b]暗号学の進歩におけるMerkle、R。、「一方向ハッシュ関数とDES」-CRYPTO '89 Proceedings、Lecture Notes in Computer Science Vol。 435、DOI 10.1007 / 0-387-34805-0_40、1990。
[Fluhrer17] Fluhrer, S., "Further Analysis of a Proposed Hash-Based Signature Standard", Cryptology ePrint Archive Report 2017/553, 2017, <https://eprint.iacr.org/2017/553>.
[Fluhrer17] Fluhrer、S.、「提案されたハッシュベースの署名標準のさらなる分析」、Cryptology ePrint Archive Report 2017 / 553、2017、<https://eprint.iacr.org/2017/553>。
[Katz16] Katz, J., "Analysis of a Proposed Hash-Based Signature Standard", in SSR 2016: Security Standardisation Research (SSR) pp. 261-273, Lecture Notes in Computer Science Vol. 10074, DOI 10.1007/978-3-319-49100-4_12, 2016.
[Katz16] Katz、J。、「提案されたハッシュベースの署名標準の分析」、SSR 2016：Security Standardization Research（SSR）pp。261-273、Lecture Notes in Computer Science Vol。 10074、DOI 10.1007 / 978-3-319-49100-4_12、2016。
[Merkle79] Merkle, R., "Secrecy, Authentication, and Public Key Systems", Technical Report No. 1979-1, Information Systems Laboratory, Stanford University, 1979, <http://www.merkle.com/papers/Thesis1979.pdf>.
[Merkle79]マークルR.、「秘密、認証、公開鍵システム」、テクニカルレポートNo. 1979-1、スタンフォード大学情報システム研究所、1979、<http://www.merkle.com/papers/Thesis1979 .pdf>。
[RFC8391] Huelsing, A., Butin, D., Gazdag, S., Rijneveld, J., and A. Mohaisen, "XMSS: eXtended Merkle Signature Scheme", RFC 8391, DOI 10.17487/RFC8391, May 2018, <https://www.rfc-editor.org/info/rfc8391>.
[RFC8391] Huelsing、A.、Butin、D.、Gazdag、S.、Rijneveld、J。、およびA. Mohaisen、「XMSS：eXtended Merkle Signature Scheme」、RFC 8391、DOI 10.17487 / RFC8391、2018年5月、<https ：//www.rfc-editor.org/info/rfc8391>。
[STMGMT] McGrew, D., Kampanakis, P., Fluhrer, S., Gazdag, S., Butin, D., and J. Buchmann, "State Management for Hash-Based Signatures.", in SSR 2016: Security Standardisation Research (SSR) pp. 244-260, Lecture Notes in Computer Science Vol. 10074, DOI 10.1007/978-3-319-49100-4_11, 2016.
[STMGMT] McGrew、D.、Kampanakis、P.、Fluhrer、S.、Gazdag、S.、Butin、D。、およびJ. Buchmann、「State Management for Hash-Based Signatures。」、SSR 2016：Security Standardization Research（SSR）pp。244-260、Lecture Notes in Computer Science Vol。 10074、DOI 10.1007 / 978-3-319-49100-4_11、2016。
[XMSS] Buchmann, J., Dahmen, E., and , "XMSS -- A Practical Forward Secure Signature Scheme Based on Minimal Security Assumptions.", in PQCrypto 2011: Post-Quantum Cryptography pp. 117-129, Lecture Notes in Computer Science Vol. 7071, DOI 10.1007/978-3-642-25405-5_8, 2011.
[XMSS] Buchmann、J.、Dahmen、E。、および、「XMSS-最小限のセキュリティ仮定に基づく実用的なフォワードセキュア署名方式」、PQCrypto 2011：Post-Quantum Cryptography pp。117-129、Lecture Notes inコンピュータサイエンスVol。 7071、DOI 10.1007 / 978-3-642-25405-5_8、2011。
An implementation MAY use the following pseudorandom process for generating an LMS private key.
実装は、LMS秘密鍵を生成するために次の擬似ランダムプロセスを使用してもよい（MAY）。
SEED is an m-byte value that is generated uniformly at random at the start of the process,
SEEDは、プロセスの開始時にランダムに均一に生成されるmバイトの値です。
I is the LMS key pair identifier,
私はLMS鍵ペアの識別子です。
q denotes the LMS leaf number of an LM-OTS private key,
qは、LM-OTS秘密鍵のLMSリーフ番号を示します。
x_q denotes the x array of private elements in the LM-OTS private key with leaf number q,
x_qは、リーフ番号qのLM-OTS秘密鍵の秘密要素のx配列を示します。
i is the index of the private key element, and
iは秘密鍵要素のインデックスであり、
H is the hash function used in LM-OTS.
HはLM-OTSで使用されるハッシュ関数です。
The elements of the LM-OTS private keys are computed as:
LM-OTS秘密鍵の要素は、次のように計算されます。
x_q[i] = H(I || u32str(q) || u16str(i) || u8str(0xff) || SEED).
x_q [i] = H（I || u32str（q）|| u16str（i）|| u8str（0xff）|| SEED）。
This process stretches the m-byte random value SEED into a (much larger) set of pseudorandom values, using a unique counter in each invocation of H. The format of the inputs to H are chosen so that they are distinct from all other uses of H in LMS and LM-OTS. A careful reader will note that this is similar to the hash we perform when iterating through the Winternitz chain; however, in that chain, the iteration index will vary between 0 and 254 maximum (for W=8), while the corresponding value in this formula is 255. This algorithm is included in the proof of security in [Fluhrer17] and hence this method is safe when used within the LMS system; however, any other cryptographically secure method of generating private keys would also be safe.
このプロセスは、Hの呼び出しごとに一意のカウンターを使用して、mバイトのランダム値SEEDを（はるかに大きい）擬似ランダム値のセットに引き伸ばします。Hへの入力の形式は、他のすべての使用と区別されるように選択されます。 LMSおよびLM-OTSのH。注意深い読者は、これがWinternitzチェーンを反復するときに実行するハッシュに似ていることに気付くでしょう。ただし、そのチェーンでは、反復インデックスは最大0〜254（W = 8の場合）の間で変化しますが、この式の対応する値は255です。このアルゴリズムは[Fluhrer17]のセキュリティの証明に含まれているため、このメソッドLMSシステム内で使用すると安全です。ただし、秘密鍵を生成する他の暗号的に安全な方法も安全です。
The LM-OTS one-time signature method uses several internal parameters, which are a function of the selected parameter set. These internal parameters include the following:
LM-OTSワンタイム署名方式は、選択されたパラメーターセットの関数であるいくつかの内部パラメーターを使用します。これらの内部パラメーターには、次のものがあります。
p This is the number of independent Winternitz chains used in the signature; it will be the number of w-bit digits needed to hold the n-bit hash (u in the below equations), along with the number of digits needed to hold the checksum (v in the below equations)
pこれは、署名で使用される独立したWinternitzチェーンの数です。これは、チェックサムを保持するのに必要な桁数（以下の方程式のv）と共に、nビットのハッシュを保持するのに必要なwビットの桁数（以下の方程式のu）になります。
ls This is the size of the shift needed to move the checksum so that it appears in the checksum digits
lsこれは、チェックサムの桁に表示されるようにチェックサムを移動するために必要なシフトのサイズです。
ls is needed because, while we express the checksum internally as a 16-bit value, we don't always express all 16 bits in the signature; for example, if w=4, we might use only the top 12 bits. Because we read the checksum in network order, this means that, without the shift, we'll use the higher-order bits (which may be always 0) and omit the lower-order bits (where the checksum value actually resides). This shift is here to ensure that the parts of the checksum we need to express (for security) actually contribute to the signature; when multiple such shifts are possible, we take the minimal value.
チェックサムを内部的に16ビット値として表現する一方で、署名内のすべての16ビットを常に表現するとは限らないため、lsが必要です。たとえば、w = 4の場合、上位12ビットのみを使用する可能性があります。チェックサムをネットワーク順に読み取るため、シフトなしで上位ビット（常に0になる場合があります）を使用し、下位ビット（チェックサム値が実際に存在するビット）を省略します。このシフトは、（セキュリティのために）表現する必要があるチェックサムの部分が実際に署名に貢献するようにするためのものです。そのような複数のシフトが可能な場合は、最小値を使用します。
The parameters ls and p are computed as follows:
パラメータlsおよびpは次のように計算されます。
u = ceil(8*n/w)
v = ceil((floor(lg((2^w - 1) * u)) + 1) / w)
ls = 16 - (v * w)
p = u + v
Here, u and v represent the number of w-bit fields required to contain the hash of the message and the checksum byte strings, respectively. And as the value of p is the number of w-bit elements of ( H(message) || Cksm(H(message)) ), it is also equivalently the number of byte strings that form the private key and the number of byte strings in the signature. The value 16 in the ls computation of ls corresponds to the 16-bit value used for the sum variable in Algorithm 2 in Section 4.4
ここで、uとvは、それぞれメッセージのハッシュとチェックサムバイト文字列を含めるために必要なwビットフィールドの数を表します。また、pの値は（H（メッセージ）|| Cksm（H（メッセージ）））のwビット要素の数であるため、これは同等に、秘密鍵を構成するバイト文字列の数とバイト数署名の文字列。 lsのls計算の値16は、セクション4.4のアルゴリズム2の合計変数に使用される16ビット値に対応します
A table illustrating various combinations of n and w with the associated values of u, v, ls, and p is provided in Table 6.
nとwのさまざまな組み合わせと、u、v、ls、およびpの関連する値を示す表を表6に示します。
+---------+------------+-----------+-----------+-------+------------+
| Hash | Winternitz | w-bit | w-bit | Left | Total |
| Length | Parameter | Elements | Elements | Shift | Number of |
| in | (w) | in Hash | in | (ls) | w-bit |
| Bytes | | (u) | Checksum | | Elements |
| (n) | | | (v) | | (p) |
+---------+------------+-----------+-----------+-------+------------+
| 32 | 1 | 256 | 9 | 7 | 265 |
| | | | | | |
| 32 | 2 | 128 | 5 | 6 | 133 |
| | | | | | |
| 32 | 4 | 64 | 3 | 4 | 67 |
| | | | | | |
| 32 | 8 | 32 | 2 | 0 | 34 |
+---------+------------+-----------+-----------+-------+------------+
Table 6
表6
The LMS public key can be computed using the following algorithm or any equivalent method. The algorithm uses a stack of hashes for data. It also makes use of a hash function with the typical init/update/final interface to hash functions; the result of the invocations hash_init(), hash_update(N[1]), hash_update(N[2]), ... , hash_update(N[n]), v = hash_final(), in that order, is identical to that of the invocation of H(N[1] || N[2] || ... || N[n]).
LMS公開鍵は、次のアルゴリズムまたは同等の方法を使用して計算できます。アルゴリズムは、データのハッシュのスタックを使用します。また、ハッシュ関数への典型的なinit / update / finalインターフェースでハッシュ関数を利用します。呼び出しの結果、hash_init()、hash_update（N [1]）、hash_update（N [2]）、...、hash_update（N [n]）、v = hash_final()は、次と同じです。 H（N [1] || N [2] || ... || N [n]）の呼び出しのそれ。
Generating an LMS Public Key from an LMS Private Key
LMS秘密鍵からLMS公開鍵を生成する
for ( i = 0; i < 2^h; i = i + 1 ) {
r = i + num_lmots_keys;
temp = H(I || u32str(r) || u16str(D_LEAF) || OTS_PUB_HASH[i])
j = i;
while (j % 2 == 1) {
r = (r - 1)/2;
j = (j-1) / 2;
left_side = pop(data stack);
temp = H(I || u32str(r) || u16str(D_INTR) || left_side || temp)
}
push temp onto the data stack
}
public_key = pop(data stack)
Note that this pseudocode expects that all 2^h leaves of the tree have equal depth -- that is, it expects num_lmots_keys to be a power of 2. The maximum depth of the stack will be h-1 elements -- that is, a total of (h-1)*n bytes; for the currently defined parameter sets, this will never be more than 768 bytes of data.
この疑似コードは、ツリーのすべての2 ^ hリーフの深さが等しいことを期待していることに注意してください。つまり、num_lmots_keysは2の累乗であると想定しています。スタックの最大の深さはh-1要素になります-つまり、合計（h-1）* nバイト。現在定義されているパラメータセットの場合、これは768バイトを超えるデータにはなりません。
The LMS signature consists of u32str(q) || lmots_signature || u32str(type) || path[0] || path[1] || ... || path[h-1]. This appendix shows one method of constructing this signature, assuming that the implementation has stored the T[] array that was used to construct the public key. Note that this is not the only possible method; other methods exist that don't assume that you have the entire T[] array in memory. To construct a signature, you perform the following algorithm:
LMS署名はu32str（q）で構成されます|| lmots_signature || u32str（タイプ）||パス[0] ||パス[1] || ... ||パス[h-1]。この付録では、実装が公開鍵の構築に使用されたT []配列を格納していると想定して、この署名を構築する1つの方法を示します。これが唯一の可能な方法ではないことに注意してください。 T []配列全体がメモリ内にあると想定しない他のメソッドが存在します。署名を作成するには、次のアルゴリズムを実行します。
Generating an LMS Signature
LMS署名の生成
1. Set type to the typecode of the LMS algorithm.
1. typeをLMSアルゴリズムのタイプコードに設定します。
2. Extract h from the typecode, according to Table 2.
2. 表2に従って、タイプコードからhを抽出します。
3. Create the LM-OTS signature for the message: ots_signature = lmots_sign(message, LMS_PRIV[q])
3. メッセージのLM-OTS署名を作成します。ots_signature= lmots_sign（message、LMS_PRIV [q]）
4. Compute the array path as follows: i = 0 r = 2^h + q while (i < h) { temp = (r / 2^i) xor 1 path[i] = T[temp] i = i + 1 }
4. 次のように配列パスを計算します。i= 0 r = 2 ^ h + q while（i <h）{temp =（r / 2 ^ i）xor 1 path [i] = T [temp] i = i + 1}
5. S = u32str(q) || ots_signature || u32str(type) || path[0] || path[1] || ... || path[h-1]
5. S = u32str（q）|| ots_signature || u32str（タイプ）||パス[0] ||パス[1] || ... ||パス[h-1]
6. q = q + 1
6. q = q + 1
7. Return S.
7. 戻り値。
Here "xor" is the bitwise exclusive-or operation, and / is integer division (that is, rounded down to an integer value).
ここで「xor」はビット単位の排他的論理和演算であり、/は整数除算です（つまり、整数値に切り捨てられます）。
An example implementation can be found online at <https://github.com/cisco/hash-sigs>.
実装例は、<https://github.com/cisco/hash-sigs>からオンラインで入手できます。
This section provides test cases that can be used to verify or debug an implementation. This data is formatted with the name of the elements on the left and the hexadecimal value of the elements on the right. The concatenation of all of the values within a public key or signature produces that public key or signature, and values that do not fit within a single line are listed across successive lines.
このセクションでは、実装の検証またはデバッグに使用できるテストケースを提供します。このデータは、左側の要素の名前と右側の要素の16進値でフォーマットされます。公開鍵または署名内のすべての値を連結すると、その公開鍵または署名が生成され、1行に収まらない値は連続する行にリストされます。
Test Case 1 Public Key
テストケース1公開キー
--------------------------------------------
HSS public key
levels 00000002
--------------------------------------------
LMS type 00000005 # LM_SHA256_M32_H5
LMOTS type 00000004 # LMOTS_SHA256_N32_W8
I 61a5d57d37f5e46bfb7520806b07a1b8
K 50650e3b31fe4a773ea29a07f09cf2ea
30e579f0df58ef8e298da0434cb2b878
--------------------------------------------
--------------------------------------------
Test Case 1 Message
テストケース1メッセージ
--------------------------------------------
Message 54686520706f77657273206e6f742064 |The powers not d|
656c65676174656420746f2074686520 |elegated to the |
556e6974656420537461746573206279 |United States by|
2074686520436f6e737469747574696f | the Constitutio|
6e2c206e6f722070726f686962697465 |n, nor prohibite|
6420627920697420746f207468652053 |d by it to the S|
74617465732c20617265207265736572 |tates, are reser|
76656420746f20746865205374617465 |ved to the State|
7320726573706563746976656c792c20 |s respectively, |
6f7220746f207468652070656f706c65 |or to the people|
2e0a |..|
--------------------------------------------
Test Case 1 Signature
--------------------------------------------
HSS signature
Nspk 00000001
sig[0]:
--------------------------------------------
LMS signature
q 00000005
--------------------------------------------
LMOTS signature
LMOTS type 00000004 # LMOTS_SHA256_N32_W8
C d32b56671d7eb98833c49b433c272586
bc4a1c8a8970528ffa04b966f9426eb9
y[0] 965a25bfd37f196b9073f3d4a232feb6
9128ec45146f86292f9dff9610a7bf95
y[1] a64c7f60f6261a62043f86c70324b770
7f5b4a8a6e19c114c7be866d488778a0
y[2] e05fd5c6509a6e61d559cf1a77a970de
927d60c70d3de31a7fa0100994e162a2
y[3] 582e8ff1b10cd99d4e8e413ef469559f
7d7ed12c838342f9b9c96b83a4943d16
y[4] 81d84b15357ff48ca579f19f5e71f184
66f2bbef4bf660c2518eb20de2f66e3b
y[5] 14784269d7d876f5d35d3fbfc7039a46
2c716bb9f6891a7f41ad133e9e1f6d95
y[6] 60b960e7777c52f060492f2d7c660e14
71e07e72655562035abc9a701b473ecb
y[7] c3943c6b9c4f2405a3cb8bf8a691ca51
d3f6ad2f428bab6f3a30f55dd9625563
y[8] f0a75ee390e385e3ae0b906961ecf41a
e073a0590c2eb6204f44831c26dd768c
y[9] 35b167b28ce8dc988a3748255230cef9
9ebf14e730632f27414489808afab1d1
y[10] e783ed04516de012498682212b078105
79b250365941bcc98142da13609e9768
y[11] aaf65de7620dabec29eb82a17fde35af
15ad238c73f81bdb8dec2fc0e7f93270
y[12] 1099762b37f43c4a3c20010a3d72e2f6
06be108d310e639f09ce7286800d9ef8
y[13] a1a40281cc5a7ea98d2adc7c7400c2fe
5a101552df4e3cccfd0cbf2ddf5dc677
y[14] 9cbbc68fee0c3efe4ec22b83a2caa3e4
8e0809a0a750b73ccdcf3c79e6580c15
y[15] 4f8a58f7f24335eec5c5eb5e0cf01dcf
4439424095fceb077f66ded5bec73b27
y[16] c5b9f64a2a9af2f07c05e99e5cf80f00
252e39db32f6c19674f190c9fbc506d8
y[17] 26857713afd2ca6bb85cd8c107347552
f30575a5417816ab4db3f603f2df56fb
y[18] c413e7d0acd8bdd81352b2471fc1bc4f
1ef296fea1220403466b1afe78b94f7e
y[19] cf7cc62fb92be14f18c2192384ebceaf
8801afdf947f698ce9c6ceb696ed70e9
y[20] e87b0144417e8d7baf25eb5f70f09f01
6fc925b4db048ab8d8cb2a661ce3b57a
y[21] da67571f5dd546fc22cb1f97e0ebd1a6
5926b1234fd04f171cf469c76b884cf3
y[22] 115cce6f792cc84e36da58960c5f1d76
0f32c12faef477e94c92eb75625b6a37
y[23] 1efc72d60ca5e908b3a7dd69fef02491
50e3eebdfed39cbdc3ce9704882a2072
y[24] c75e13527b7a581a556168783dc1e975
45e31865ddc46b3c957835da252bb732
y[25] 8d3ee2062445dfb85ef8c35f8e1f3371
af34023cef626e0af1e0bc017351aae2
y[26] ab8f5c612ead0b729a1d059d02bfe18e
fa971b7300e882360a93b025ff97e9e0
y[27] eec0f3f3f13039a17f88b0cf808f4884
31606cb13f9241f40f44e537d302c64a
y[28] 4f1f4ab949b9feefadcb71ab50ef27d6
d6ca8510f150c85fb525bf25703df720
y[29] 9b6066f09c37280d59128d2f0f637c7d
7d7fad4ed1c1ea04e628d221e3d8db77
y[30] b7c878c9411cafc5071a34a00f4cf077
38912753dfce48f07576f0d4f94f42c6
y[31] d76f7ce973e9367095ba7e9a3649b7f4
61d9f9ac1332a4d1044c96aefee67676
y[32] 401b64457c54d65fef6500c59cdfb69a
f7b6dddfcb0f086278dd8ad0686078df
y[33] b0f3f79cd893d314168648499898fbc0
ced5f95b74e8ff14d735cdea968bee74
--------------------------------------------
LMS type 00000005 # LM_SHA256_M32_H5
path[0] d8b8112f9200a5e50c4a262165bd342c
d800b8496810bc716277435ac376728d
path[1] 129ac6eda839a6f357b5a04387c5ce97
382a78f2a4372917eefcbf93f63bb591
path[2] 12f5dbe400bd49e4501e859f885bf073
6e90a509b30a26bfac8c17b5991c157e
path[3] b5971115aa39efd8d564a6b90282c316
8af2d30ef89d51bf14654510a12b8a14
path[4] 4cca1848cf7da59cc2b3d9d0692dd2a2
0ba3863480e25b1b85ee860c62bf5136
--------------------------------------------
LMS public key
LMS type 00000005 # LM_SHA256_M32_H5
LMOTS type 00000004 # LMOTS_SHA256_N32_W8
I d2f14ff6346af964569f7d6cb880a1b6
K 6c5004917da6eafe4d9ef6c6407b3db0
e5485b122d9ebe15cda93cfec582d7ab
--------------------------------------------
final_signature:
--------------------------------------------
LMS signature
q 0000000a
--------------------------------------------
LMOTS signature
LMOTS type 00000004 # LMOTS_SHA256_N32_W8
C 0703c491e7558b35011ece3592eaa5da
4d918786771233e8353bc4f62323185c
y[0] 95cae05b899e35dffd71705470620998
8ebfdf6e37960bb5c38d7657e8bffeef
y[1] 9bc042da4b4525650485c66d0ce19b31
7587c6ba4bffcc428e25d08931e72dfb
y[2] 6a120c5612344258b85efdb7db1db9e1
865a73caf96557eb39ed3e3f426933ac
y[3] 9eeddb03a1d2374af7bf771855774562
37f9de2d60113c23f846df26fa942008
y[4] a698994c0827d90e86d43e0df7f4bfcd
b09b86a373b98288b7094ad81a0185ac
y[5] 100e4f2c5fc38c003c1ab6fea479eb2f
5ebe48f584d7159b8ada03586e65ad9c
y[6] 969f6aecbfe44cf356888a7b15a3ff07
4f771760b26f9c04884ee1faa329fbf4
y[7] e61af23aee7fa5d4d9a5dfcf43c4c26c
e8aea2ce8a2990d7ba7b57108b47dabf
y[8] beadb2b25b3cacc1ac0cef346cbb90fb
044beee4fac2603a442bdf7e507243b7
y[9] 319c9944b1586e899d431c7f91bcccc8
690dbf59b28386b2315f3d36ef2eaa3c
y[10] f30b2b51f48b71b003dfb08249484201
043f65f5a3ef6bbd61ddfee81aca9ce6
y[11] 0081262a00000480dcbc9a3da6fbef5c
1c0a55e48a0e729f9184fcb1407c3152
y[12] 9db268f6fe50032a363c9801306837fa
fabdf957fd97eafc80dbd165e435d0e2
y[13] dfd836a28b354023924b6fb7e48bc0b3
ed95eea64c2d402f4d734c8dc26f3ac5
y[14] 91825daef01eae3c38e3328d00a77dc6
57034f287ccb0f0e1c9a7cbdc828f627
y[15] 205e4737b84b58376551d44c12c3c215
c812a0970789c83de51d6ad787271963
y[16] 327f0a5fbb6b5907dec02c9a90934af5
a1c63b72c82653605d1dcce51596b3c2
y[17] b45696689f2eb382007497557692caac
4d57b5de9f5569bc2ad0137fd47fb47e
y[18] 664fcb6db4971f5b3e07aceda9ac130e
9f38182de994cff192ec0e82fd6d4cb7
y[19] f3fe00812589b7a7ce51544045643301
6b84a59bec6619a1c6c0b37dd1450ed4
y[20] f2d8b584410ceda8025f5d2d8dd0d217
6fc1cf2cc06fa8c82bed4d944e71339e
y[21] ce780fd025bd41ec34ebff9d4270a322
4e019fcb444474d482fd2dbe75efb203
y[22] 89cc10cd600abb54c47ede93e08c114e
db04117d714dc1d525e11bed8756192f
y[23] 929d15462b939ff3f52f2252da2ed64d
8fae88818b1efa2c7b08c8794fb1b214
y[24] aa233db3162833141ea4383f1a6f120b
e1db82ce3630b3429114463157a64e91
y[25] 234d475e2f79cbf05e4db6a9407d72c6
bff7d1198b5c4d6aad2831db61274993
y[26] 715a0182c7dc8089e32c8531deed4f74
31c07c02195eba2ef91efb5613c37af7
y[27] ae0c066babc69369700e1dd26eddc0d2
16c781d56e4ce47e3303fa73007ff7b9
y[28] 49ef23be2aa4dbf25206fe45c20dd888
395b2526391a724996a44156beac8082
y[29] 12858792bf8e74cba49dee5e8812e019
da87454bff9e847ed83db07af3137430
y[30] 82f880a278f682c2bd0ad6887cb59f65
2e155987d61bbf6a88d36ee93b6072e6
y[31] 656d9ccbaae3d655852e38deb3a2dcf8
058dc9fb6f2ab3d3b3539eb77b248a66
y[32] 1091d05eb6e2f297774fe6053598457c
c61908318de4b826f0fc86d4bb117d33
y[33] e865aa805009cc2918d9c2f840c4da43
a703ad9f5b5806163d7161696b5a0adc
--------------------------------------------
LMS type 00000005 # LM_SHA256_M32_H5
path[0] d5c0d1bebb06048ed6fe2ef2c6cef305
b3ed633941ebc8b3bec9738754cddd60
path[1] e1920ada52f43d055b5031cee6192520
d6a5115514851ce7fd448d4a39fae2ab
path[2] 2335b525f484e9b40d6a4a969394843b
dcf6d14c48e8015e08ab92662c05c6e9
path[3] f90b65a7a6201689999f32bfd368e5e3
ec9cb70ac7b8399003f175c40885081a
path[4] 09ab3034911fe125631051df0408b394
6b0bde790911e8978ba07dd56c73e7ee
Test Case 2 Private Key
テストケース2秘密鍵
--------------------------------------------
(note: procedure in Appendix A is used)
Top level LMS tree
SEED 558b8966c48ae9cb898b423c83443aae
014a72f1b1ab5cc85cf1d892903b5439
I d08fabd4a2091ff0a8cb4ed834e74534
Second level LMS tree
SEED a1c4696e2608035a886100d05cd99945
eb3370731884a8235e2fb3d4d71f2547
I 215f83b7ccb9acbcd08db97b0d04dc2b
--------------------------------------------
--------------------------------------------
Test Case 2 Public Key
テストケース2公開キー
--------------------------------------------
HSS public key
levels 00000002
--------------------------------------------
LMS type 00000006 # LM_SHA256_M32_H10
LMOTS type 00000003 # LMOTS_SHA256_N32_W4
I d08fabd4a2091ff0a8cb4ed834e74534
K 32a58885cd9ba0431235466bff9651c6
c92124404d45fa53cf161c28f1ad5a8e
--------------------------------------------
--------------------------------------------
Test Case 2 Message
テストケース2メッセージ
--------------------------------------------
Message 54686520656e756d65726174696f6e20 |The enumeration |
696e2074686520436f6e737469747574 |in the Constitut|
696f6e2c206f66206365727461696e20 |ion, of certain |
7269676874732c207368616c6c206e6f |rights, shall no|
7420626520636f6e7374727565642074 |t be construed t|
6f2064656e79206f7220646973706172 |o deny or dispar|
616765206f7468657273207265746169 |age others retai|
6e6564206279207468652070656f706c |ned by the peopl|
652e0a |e..|
--------------------------------------------
Test Case 2 Signature
--------------------------------------------
HSS signature
Nspk 00000001
sig[0]:
--------------------------------------------
LMS signature
q 00000003
--------------------------------------------
LMOTS signature
LMOTS type 00000003 # LMOTS_SHA256_N32_W4
C 3d46bee8660f8f215d3f96408a7a64cf
1c4da02b63a55f62c666ef5707a914ce
y[0] 0674e8cb7a55f0c48d484f31f3aa4af9
719a74f22cf823b94431d01c926e2a76
y[1] bb71226d279700ec81c9e95fb11a0d10
d065279a5796e265ae17737c44eb8c59
y[2] 4508e126a9a7870bf4360820bdeb9a01
d9693779e416828e75bddd7d8c70d50a
y[3] 0ac8ba39810909d445f44cb5bb58de73
7e60cb4345302786ef2c6b14af212ca1
y[4] 9edeaa3bfcfe8baa6621ce88480df237
1dd37add732c9de4ea2ce0dffa53c926
y[5] 49a18d39a50788f4652987f226a1d481
68205df6ae7c58e049a25d4907edc1aa
y[6] 90da8aa5e5f7671773e941d805536021
5c6b60dd35463cf2240a9c06d694e9cb
y[7] 54e7b1e1bf494d0d1a28c0d31acc7516
1f4f485dfd3cb9578e836ec2dc722f37
y[8] ed30872e07f2b8bd0374eb57d22c614e
09150f6c0d8774a39a6e168211035dc5
y[9] 2988ab46eaca9ec597fb18b4936e66ef
2f0df26e8d1e34da28cbb3af75231372
y[10] 0c7b345434f72d65314328bbb030d0f0
f6d5e47b28ea91008fb11b05017705a8
y[11] be3b2adb83c60a54f9d1d1b2f476f9e3
93eb5695203d2ba6ad815e6a111ea293
y[12] dcc21033f9453d49c8e5a6387f588b1e
a4f706217c151e05f55a6eb7997be09d
y[13] 56a326a32f9cba1fbe1c07bb49fa04ce
cf9df1a1b815483c75d7a27cc88ad1b1
y[14] 238e5ea986b53e087045723ce16187ed
a22e33b2c70709e53251025abde89396
y[15] 45fc8c0693e97763928f00b2e3c75af3
942d8ddaee81b59a6f1f67efda0ef81d
y[16] 11873b59137f67800b35e81b01563d18
7c4a1575a1acb92d087b517a8833383f
y[17] 05d357ef4678de0c57ff9f1b2da61dfd
e5d88318bcdde4d9061cc75c2de3cd47
y[18] 40dd7739ca3ef66f1930026f47d9ebaa
713b07176f76f953e1c2e7f8f271a6ca
y[19] 375dbfb83d719b1635a7d8a138919579
44b1c29bb101913e166e11bd5f34186f
y[20] a6c0a555c9026b256a6860f4866bd6d0
b5bf90627086c6149133f8282ce6c9b3
y[21] 622442443d5eca959d6c14ca8389d12c
4068b503e4e3c39b635bea245d9d05a2
y[22] 558f249c9661c0427d2e489ca5b5dde2
20a90333f4862aec793223c781997da9
y[23] 8266c12c50ea28b2c438e7a379eb106e
ca0c7fd6006e9bf612f3ea0a454ba3bd
y[24] b76e8027992e60de01e9094fddeb3349
883914fb17a9621ab929d970d101e45f
y[25] 8278c14b032bcab02bd15692d21b6c5c
204abbf077d465553bd6eda645e6c306
y[26] 5d33b10d518a61e15ed0f092c3222628
1a29c8a0f50cde0a8c66236e29c2f310
y[27] a375cebda1dc6bb9a1a01dae6c7aba8e
bedc6371a7d52aacb955f83bd6e4f84d
y[28] 2949dcc198fb77c7e5cdf6040b0f84fa
f82808bf985577f0a2acf2ec7ed7c0b0
y[29] ae8a270e951743ff23e0b2dd12e9c3c8
28fb5598a22461af94d568f29240ba28
y[30] 20c4591f71c088f96e095dd98beae456
579ebbba36f6d9ca2613d1c26eee4d8c
y[31] 73217ac5962b5f3147b492e8831597fd
89b64aa7fde82e1974d2f6779504dc21
y[32] 435eb3109350756b9fdabe1c6f368081
bd40b27ebcb9819a75d7df8bb07bb05d
y[33] b1bab705a4b7e37125186339464ad8fa
aa4f052cc1272919fde3e025bb64aa8e
y[34] 0eb1fcbfcc25acb5f718ce4f7c2182fb
393a1814b0e942490e52d3bca817b2b2
y[35] 6e90d4c9b0cc38608a6cef5eb153af08
58acc867c9922aed43bb67d7b33acc51
y[36] 9313d28d41a5c6fe6cf3595dd5ee63f0
a4c4065a083590b275788bee7ad875a7
y[37] f88dd73720708c6c6c0ecf1f43bbaada
e6f208557fdc07bd4ed91f88ce4c0de8
y[38] 42761c70c186bfdafafc444834bd3418
be4253a71eaf41d718753ad07754ca3e
y[39] ffd5960b0336981795721426803599ed
5b2b7516920efcbe32ada4bcf6c73bd2
y[40] 9e3fa152d9adeca36020fdeeee1b7395
21d3ea8c0da497003df1513897b0f547
y[41] 94a873670b8d93bcca2ae47e64424b74
23e1f078d9554bb5232cc6de8aae9b83
y[42] fa5b9510beb39ccf4b4e1d9c0f19d5e1
7f58e5b8705d9a6837a7d9bf99cd1338
y[43] 7af256a8491671f1f2f22af253bcff54
b673199bdb7d05d81064ef05f80f0153
y[44] d0be7919684b23da8d42ff3effdb7ca0
985033f389181f47659138003d712b5e
y[45] c0a614d31cc7487f52de8664916af79c
98456b2c94a8038083db55391e347586
y[46] 2250274a1de2584fec975fb09536792c
fbfcf6192856cc76eb5b13dc4709e2f7
y[47] 301ddff26ec1b23de2d188c999166c74
e1e14bbc15f457cf4e471ae13dcbdd9c
y[48] 50f4d646fc6278e8fe7eb6cb5c94100f
a870187380b777ed19d7868fd8ca7ceb
y[49] 7fa7d5cc861c5bdac98e7495eb0a2cee
c1924ae979f44c5390ebedddc65d6ec1
y[50] 1287d978b8df064219bc5679f7d7b264
a76ff272b2ac9f2f7cfc9fdcfb6a5142
y[51] 8240027afd9d52a79b647c90c2709e06
0ed70f87299dd798d68f4fadd3da6c51
y[52] d839f851f98f67840b964ebe73f8cec4
1572538ec6bc131034ca2894eb736b3b
y[53] da93d9f5f6fa6f6c0f03ce43362b8414
940355fb54d3dfdd03633ae108f3de3e
y[54] bc85a3ff51efeea3bc2cf27e1658f178
9ee612c83d0f5fd56f7cd071930e2946
y[55] beeecaa04dccea9f97786001475e0294
bc2852f62eb5d39bb9fbeef75916efe4
y[56] 4a662ecae37ede27e9d6eadfdeb8f8b2
b2dbccbf96fa6dbaf7321fb0e701f4d4
y[57] 29c2f4dcd153a2742574126e5eaccc77
686acf6e3ee48f423766e0fc466810a9
y[58] 05ff5453ec99897b56bc55dd49b99114
2f65043f2d744eeb935ba7f4ef23cf80
y[59] cc5a8a335d3619d781e7454826df720e
ec82e06034c44699b5f0c44a8787752e
y[60] 057fa3419b5bb0e25d30981e41cb1361
322dba8f69931cf42fad3f3bce6ded5b
y[61] 8bfc3d20a2148861b2afc14562ddd27f
12897abf0685288dcc5c4982f8260268
y[62] 46a24bf77e383c7aacab1ab692b29ed8
c018a65f3dc2b87ff619a633c41b4fad
y[63] b1c78725c1f8f922f6009787b1964247
df0136b1bc614ab575c59a16d089917b
y[64] d4a8b6f04d95c581279a139be09fcf6e
98a470a0bceca191fce476f9370021cb
y[65] c05518a7efd35d89d8577c990a5e1996
1ba16203c959c91829ba7497cffcbb4b
y[66] 294546454fa5388a23a22e805a5ca35f
956598848bda678615fec28afd5da61a
--------------------------------------------
LMS type 00000006 # LM_SHA256_M32_H10
path[0] b326493313053ced3876db9d23714818
1b7173bc7d042cefb4dbe94d2e58cd21
path[1] a769db4657a103279ba8ef3a629ca84e
e836172a9c50e51f45581741cf808315
path[2] 0b491cb4ecbbabec128e7c81a46e62a6
7b57640a0a78be1cbf7dd9d419a10cd8
path[3] 686d16621a80816bfdb5bdc56211d72c
a70b81f1117d129529a7570cf79cf52a
path[4] 7028a48538ecdd3b38d3d5d62d262465
95c4fb73a525a5ed2c30524ebb1d8cc8
path[5] 2e0c19bc4977c6898ff95fd3d310b0ba
e71696cef93c6a552456bf96e9d075e3
path[6] 83bb7543c675842bafbfc7cdb88483b3
276c29d4f0a341c2d406e40d4653b7e4
path[7] d045851acf6a0a0ea9c710b805cced46
35ee8c107362f0fc8d80c14d0ac49c51
path[8] 6703d26d14752f34c1c0d2c4247581c1
8c2cf4de48e9ce949be7c888e9caebe4
path[9] a415e291fd107d21dc1f084b11582082
49f28f4f7c7e931ba7b3bd0d824a4570
--------------------------------------------
LMS public key
LMS type 00000005 # LM_SHA256_M32_H5
LMOTS type 00000004 # LMOTS_SHA256_N32_W8
I 215f83b7ccb9acbcd08db97b0d04dc2b
K a1cd035833e0e90059603f26e07ad2aa
d152338e7a5e5984bcd5f7bb4eba40b7
--------------------------------------------
final_signature:
--------------------------------------------
LMS signature
q 00000004
--------------------------------------------
LMOTS signature
LMOTS type 00000004 # LMOTS_SHA256_N32_W8
C 0eb1ed54a2460d512388cad533138d24
0534e97b1e82d33bd927d201dfc24ebb
y[0] 11b3649023696f85150b189e50c00e98
850ac343a77b3638319c347d7310269d
y[1] 3b7714fa406b8c35b021d54d4fdada7b
9ce5d4ba5b06719e72aaf58c5aae7aca
y[2] 057aa0e2e74e7dcfd17a0823429db629
65b7d563c57b4cec942cc865e29c1dad
y[3] 83cac8b4d61aacc457f336e6a10b6632
3f5887bf3523dfcadee158503bfaa89d
y[4] c6bf59daa82afd2b5ebb2a9ca6572a60
67cee7c327e9039b3b6ea6a1edc7fdc3
y[5] df927aade10c1c9f2d5ff446450d2a39
98d0f9f6202b5e07c3f97d2458c69d3c
y[6] 8190643978d7a7f4d64e97e3f1c4a08a
7c5bc03fd55682c017e2907eab07e5bb
y[7] 2f190143475a6043d5e6d5263471f4ee
cf6e2575fbc6ff37edfa249d6cda1a09
y[8] f797fd5a3cd53a066700f45863f04b6c
8a58cfd341241e002d0d2c0217472bf1
y[9] 8b636ae547c1771368d9f317835c9b0e
f430b3df4034f6af00d0da44f4af7800
y[10] bc7a5cf8a5abdb12dc718b559b74cab9
090e33cc58a955300981c420c4da8ffd
y[11] 67df540890a062fe40dba8b2c1c548ce
d22473219c534911d48ccaabfb71bc71
y[12] 862f4a24ebd376d288fd4e6fb06ed870
5787c5fedc813cd2697e5b1aac1ced45
y[13] 767b14ce88409eaebb601a93559aae89
3e143d1c395bc326da821d79a9ed41dc
y[14] fbe549147f71c092f4f3ac522b5cc572
90706650487bae9bb5671ecc9ccc2ce5
y[15] 1ead87ac01985268521222fb9057df7e
d41810b5ef0d4f7cc67368c90f573b1a
y[16] c2ce956c365ed38e893ce7b2fae15d36
85a3df2fa3d4cc098fa57dd60d2c9754
y[17] a8ade980ad0f93f6787075c3f680a2ba
1936a8c61d1af52ab7e21f416be09d2a
y[18] 8d64c3d3d8582968c2839902229f85ae
e297e717c094c8df4a23bb5db658dd37
y[19] 7bf0f4ff3ffd8fba5e383a48574802ed
545bbe7a6b4753533353d73706067640
y[20] 135a7ce517279cd683039747d218647c
86e097b0daa2872d54b8f3e508598762
y[21] 9547b830d8118161b65079fe7bc59a99
e9c3c7380e3e70b7138fe5d9be255150
y[22] 2b698d09ae193972f27d40f38dea264a
0126e637d74ae4c92a6249fa103436d3
y[23] eb0d4029ac712bfc7a5eacbdd7518d6d
4fe903a5ae65527cd65bb0d4e9925ca2
y[24] 4fd7214dc617c150544e423f450c99ce
51ac8005d33acd74f1bed3b17b7266a4
y[25] a3bb86da7eba80b101e15cb79de9a207
852cf91249ef480619ff2af8cabca831
y[26] 25d1faa94cbb0a03a906f683b3f47a97
c871fd513e510a7a25f283b196075778
y[27] 496152a91c2bf9da76ebe089f4654877
f2d586ae7149c406e663eadeb2b5c7e8
y[28] 2429b9e8cb4834c83464f079995332e4
b3c8f5a72bb4b8c6f74b0d45dc6c1f79
y[29] 952c0b7420df525e37c15377b5f09843
19c3993921e5ccd97e097592064530d3
y[30] 3de3afad5733cbe7703c5296263f7734
2efbf5a04755b0b3c997c4328463e84c
y[31] aa2de3ffdcd297baaaacd7ae646e44b5
c0f16044df38fabd296a47b3a838a913
y[32] 982fb2e370c078edb042c84db34ce36b
46ccb76460a690cc86c302457dd1cde1
y[33] 97ec8075e82b393d542075134e2a17ee
70a5e187075d03ae3c853cff60729ba4
--------------------------------------------
LMS type 00000005 # LM_SHA256_M32_H5
path[0] 4de1f6965bdabc676c5a4dc7c35f97f8
2cb0e31c68d04f1dad96314ff09e6b3d
path[1] e96aeee300d1f68bf1bca9fc58e40323
36cd819aaf578744e50d1357a0e42867
path[2] 04d341aa0a337b19fe4bc43c2e79964d
4f351089f2e0e41c7c43ae0d49e7f404
path[3] b0f75be80ea3af098c9752420a8ac0ea
2bbb1f4eeba05238aef0d8ce63f0c6e5
path[4] e4041d95398a6f7f3e0ee97cc1591849
d4ed236338b147abde9f51ef9fd4e1c1
Acknowledgements
謝辞
Thanks are due to Chirag Shroff, Andreas Huelsing, Burt Kaliski, Eric Osterweil, Ahmed Kosba, Russ Housley, Philip Lafrance, Alexander Truskovsky, Mark Peruzel, and Jim Schaad for constructive suggestions and valuable detailed review. We especially acknowledge Jerry Solinas, Laurie Law, and Kevin Igoe, who pointed out the security benefits of the approach of Leighton and Micali [USPTO5432852], Jonathan Katz, who gave us security guidance, and Bruno Couillard and Jim Goodman for an especially thorough review.
建設的な提案と貴重な詳細なレビューを提供してくれたChirag Shroff、Andreas Huelsing、Burt Kaliski、Eric Osterweil、Ahmed Kosba、Russ Housley、Philip Lafrance、Alexander Truskovsky、Mark Peruzel、Jim Schaadに感謝します。私たちは特に、レイトンとミカリ[USPTO5432852]のアプローチのセキュリティ上の利点を指摘したジェリーソリナス、ローリーロー、ケビンイゴエ、セキュリティガイダンスを提供してくれたジョナサンカッツ、特に徹底的なレビューをしてくれたブルーノクイヤールとジムグッドマンに感謝します。 。
Authors' Addresses
著者のアドレス
David McGrew Cisco Systems 13600 Dulles Technology Drive Herndon, VA 20171 United States of America
David McGrew Cisco Systems 13600 Dulles Technology Drive Herndon、VA 20171アメリカ合衆国
Email: mcgrew@cisco.com
Michael Curcio Cisco Systems 7025-2 Kit Creek Road Research Triangle Park, NC 27709-4987 United States of America
Michael Curcio Cisco Systems 7025-2 Kit Creek Road Research Triangle Park、NC 27709-4987アメリカ合衆国
Email: micurcio@cisco.com
Scott Fluhrer Cisco Systems 170 West Tasman Drive San Jose, CA United States of America
Scott Fluhrer Cisco Systems 170 West Tasman Driveサンノゼ、カリフォルニア州アメリカ合衆国
Email: sfluhrer@cisco.com