Some lattice attacks on DSA and ECDSA (Q429782): Difference between revisions

From MaRDI portal
Importer (talk | contribs)
Created a new Item
 
ReferenceBot (talk | contribs)
Changed an Item
 
(4 intermediate revisions by 4 users not shown)
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
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1007/s00200-011-0154-4 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W1971773630 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4364558 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4265362 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the security of the digital signature algorithm / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q2766810 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Small solutions to polynomial equations, and low exponent RSA vulnerabilities / rank
 
Normal rank
Property / cites work
 
Property / cites work: A public key cryptosystem and a signature scheme based on discrete logarithms / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3856819 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4400575 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Lattice attacks on digital signature schemes / rank
 
Normal rank
Property / cites work
 
Property / cites work: The state of elliptic curve cryptography / rank
 
Normal rank
Property / cites work
 
Property / cites work: A Survey of Public-Key Cryptosystems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Factoring polynomials with rational coefficients / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4718481 / rank
 
Normal rank
Property / cites work
 
Property / cites work: The insecurity of the digital signature algorithm with partially known nonces / rank
 
Normal rank
Property / cites work
 
Property / cites work: The insecurity of the elliptic curve digital signature algorithm with partially known nonces / rank
 
Normal rank
Property / cites work
 
Property / cites work: A variant of digital signature algorithm / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q2770462 / rank
 
Normal rank
links / mardi / namelinks / mardi / name
 

Latest revision as of 08:42, 5 July 2024

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
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references