Some lattice attacks on DSA and ECDSA (Q429782): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
Property / review text | |||
This paper develops attacks on DSA and ECDSA using the algorithm for LLL reduction and two algorithms for the computation of the integral points of two classes of conics, provided that the secret and the ephemeral key of a signed message or their modular inverses are sufficiently small and in case the ephemeral keys or their modular inverses of two signed messages are sufficiently small. These attacks are based on the equality \(s=k^{-1}(h(m)+ar)\bmod q\). Assuming that a signature is available and each number in at least one of the sets \(\{a, k^{-1}\bmod q\}\), \(\{k, a^{-1}\bmod q\}\) and \(\{a^{-1}\bmod q, k^{-1}\bmod q\}\) is smaller or larger than a certain explicit bound, the secret keys \(a\) and \(k\) can be revealed. Moreover, if two signatures with ephemeral keys \(k_1\) and \(k_2\) are available and each number in at least one of the sets \(\{k_1, k_2^{-1}\bmod q\}\), \(\{k_2, k_1^{-1}\bmod q\}\) and \(\{k_1^{-1}\bmod q, k_2^{-1}\bmod q\}\) is smaller or larger than a certain explicit bound, then \(k_1\), \(k_2\) and subsequently \(a\) can be computed. | |||
Property / review text: This paper develops attacks on DSA and ECDSA using the algorithm for LLL reduction and two algorithms for the computation of the integral points of two classes of conics, provided that the secret and the ephemeral key of a signed message or their modular inverses are sufficiently small and in case the ephemeral keys or their modular inverses of two signed messages are sufficiently small. These attacks are based on the equality \(s=k^{-1}(h(m)+ar)\bmod q\). Assuming that a signature is available and each number in at least one of the sets \(\{a, k^{-1}\bmod q\}\), \(\{k, a^{-1}\bmod q\}\) and \(\{a^{-1}\bmod q, k^{-1}\bmod q\}\) is smaller or larger than a certain explicit bound, the secret keys \(a\) and \(k\) can be revealed. Moreover, if two signatures with ephemeral keys \(k_1\) and \(k_2\) are available and each number in at least one of the sets \(\{k_1, k_2^{-1}\bmod q\}\), \(\{k_2, k_1^{-1}\bmod q\}\) and \(\{k_1^{-1}\bmod q, k_2^{-1}\bmod q\}\) is smaller or larger than a certain explicit bound, then \(k_1\), \(k_2\) and subsequently \(a\) can be computed. / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Vladimír Lacko / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 94A60 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 11T71 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 11Y16 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 94A62 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6048439 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
public key cryptography | |||
Property / zbMATH Keywords: public key cryptography / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
digital signature algorithm | |||
Property / zbMATH Keywords: digital signature algorithm / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
elliptic curve algorithm LLL | |||
Property / zbMATH Keywords: elliptic curve algorithm LLL / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
discrete logarithm | |||
Property / zbMATH Keywords: discrete logarithm / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Diophantine equations | |||
Property / zbMATH Keywords: Diophantine equations / rank | |||
Normal rank |
Revision as of 23:37, 29 June 2023
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Some lattice attacks on DSA and ECDSA |
scientific article |
Statements
Some lattice attacks on DSA and ECDSA (English)
0 references
20 June 2012
0 references
This paper develops attacks on DSA and ECDSA using the algorithm for LLL reduction and two algorithms for the computation of the integral points of two classes of conics, provided that the secret and the ephemeral key of a signed message or their modular inverses are sufficiently small and in case the ephemeral keys or their modular inverses of two signed messages are sufficiently small. These attacks are based on the equality \(s=k^{-1}(h(m)+ar)\bmod q\). Assuming that a signature is available and each number in at least one of the sets \(\{a, k^{-1}\bmod q\}\), \(\{k, a^{-1}\bmod q\}\) and \(\{a^{-1}\bmod q, k^{-1}\bmod q\}\) is smaller or larger than a certain explicit bound, the secret keys \(a\) and \(k\) can be revealed. Moreover, if two signatures with ephemeral keys \(k_1\) and \(k_2\) are available and each number in at least one of the sets \(\{k_1, k_2^{-1}\bmod q\}\), \(\{k_2, k_1^{-1}\bmod q\}\) and \(\{k_1^{-1}\bmod q, k_2^{-1}\bmod q\}\) is smaller or larger than a certain explicit bound, then \(k_1\), \(k_2\) and subsequently \(a\) can be computed.
0 references
public key cryptography
0 references
digital signature algorithm
0 references
elliptic curve algorithm LLL
0 references
discrete logarithm
0 references
Diophantine equations
0 references