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

complexityinsecuritypolynomial congruencescomputational number theoryRSA cryptosystemalgebraic coding theorylattice algorithm

Mathematics Subject Classification ID

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

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

(27)

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

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)