How to fake an RSA signature by encoding modular root finding as a SAT problem

DOI10.1016/S0166-218X(02)00400-6MaRDI QIDQ1408375zbMATH OpenOpenAlexFDO

Authors Claudia Fiorini, Enrico Martinelli, Fabio Massacci

Publication date 15 September 2003

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0166-218x(02)00400-6

zbMATH Keywords

RSABenchmarksSatisfiabilityAutomated reasoningLogical cryptanalysisModular cube rootsModular multiplication

Mathematics Subject Classification ID

Data encryption (aspects in computer science) (68P25) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Logical cryptanalysis as a SAT problem
• Which new RSA-signatures can be computed from certain given RSA- signatures!
• Logical cryptanalysis as a SAT problem: Encoding and analysis of the U. S. Data Encryption Standard
• SAT-approach to cryptography of some stream ciphering systems
• Applications of SAT solvers in cryptanalysis: finding weak keys and preimages

Cites work

• scientific article; zbMATH DE number 1696817 (Why is no real title available?)
• scientific article; zbMATH DE number 1258344 (Why is no real title available?)
• scientific article; zbMATH DE number 475432 (Why is no real title available?)
• scientific article; zbMATH DE number 1113991 (Why is no real title available?)
• scientific article; zbMATH DE number 1467488 (Why is no real title available?)
• scientific article; zbMATH DE number 774344 (Why is no real title available?)
• A Computing Procedure for Quantification Theory
• A machine program for theorem-proving
• A method for obtaining digital signatures and public-key cryptosystems
• A two-phase algorithm for solving a class of hard satisfiability problems
• An RNS Montgomery modular multiplication algorithm
• Breaking RSA may not be equivalent to factoring
• Experimental results on the crossover point in random 3-SAT
• Generating hard satisfiability problems
• Graph-Based Algorithms for Boolean Function Manipulation
• Logic programs with stable model semantics as a constraint programming paradigm
• Logical cryptanalysis as a SAT problem: Encoding and analysis of the U. S. Data Encryption Standard
• New efficient structure for a modular multiplier for RNS
• Novel approaches to the design of VLSI RNS multipliers
• Residue multipliers using factored decomposition
• Small solutions to polynomial equations, and low exponent RSA vulnerabilities
• Solving Simultaneous Modular Equations of Low Degree
• Some pitfalls for experimenters with random SAT
• The propositional formula checker HeerHugo

Cited in

(2)

• A SAT-based preimage analysis of reduced \textsc{Keccak} hash functions
• Logical cryptanalysis as a SAT problem: Encoding and analysis of the U. S. Data Encryption Standard

Describes a project that uses

Uses Software

• HeerHugo
• Smodels

This page was built for publication: How to fake an RSA signature by encoding modular root finding as a SAT problem

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