Solving Simultaneous Modular Equations of Low Degree

DOI10.1137/0217019MaRDI QIDQ3783957zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Johan Hastad

Publication date 1988

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/51a80f6eafb9d366bf729a44acff42313eaec041

zbMATH Keywords

algebraic coding theorycomplexitycomputational number theoryinsecuritylattice algorithmpolynomial congruencesRSA cryptosystem

Mathematics Subject Classification ID

Congruences; primitive roots; residue systems (11A07) Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Cryptography (94A60)

Recommendations

• Small solutions to polynomial equations, and low exponent RSA vulnerabilities
• Successful cryptanalytic attacks upon RSA moduli N=pq
• scientific article; zbMATH DE number 4035724
• Solving Systems of Modular Equations in One Variable: How Many RSA-Encrypted Messages Does Eve Need to Know?
• scientific article; zbMATH DE number 1303120

Cited in

(29)

• Small solutions to polynomial equations, and low exponent RSA vulnerabilities
• How to fake an RSA signature by encoding modular root finding as a SAT problem
• The multi-dimension RSA and its low exponent security
• A generalized attack on RSA type cryptosystems
• On the optimality of lattices for the Coppersmith technique
• Mathematical problems in cryptology
• Solving word equations modulo partial commutations
• Efficient and tight oblivious transfer from PKE with tight multi-user security
• Cryptanalysis of RSA for a special case with \(d > e\)
• Solving low-density multiple subset sum problems with SVP oracle
• GNUC: a new universal composability framework
• Solving linear equations modulo unknown divisors: revisited
• Factoring RSA moduli with weak prime factors
• Simplified High-Speed High-Distance List Decoding for Alternant Codes
• scientific article; zbMATH DE number 4212179 (Why is no real title available?)
• On the Improvement of the BDF Attack on LSBS-RSA
• The polynomial composition problem in \((\mathbb Z/n\mathbb Z)[X]\)
• Solving Linear Equations Modulo Divisors: On Factoring Given Any Bits
• scientific article; zbMATH DE number 4035724 (Why is no real title available?)
• Reconstructing Truncated Integer Variables Satisfying Linear Congruences
• A natural lattice basis problem with applications
• scientific article; zbMATH DE number 2098573 (Why is no real title available?)
• Forty years of attacks on the RSA cryptosystem: a brief survey
• Meta-heuristic approaches to solve shortest lattice vector problem
• Using LLL-reduction for solving RSA and factorization problems
• Solving Systems of Modular Equations in One Variable: How Many RSA-Encrypted Messages Does Eve Need to Know?
• Randomness Reuse: Extensions and Improvements
• Cryptanalysis of Short Exponent RSA with Primes Sharing Least Significant Bits
• The multi-variable modular polynomial and its applications to cryptography

This page was built for publication: Solving Simultaneous Modular Equations of Low Degree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3783957)