Giter VIP home page Giter VIP logo

rsa-extending-wiener-attack's Introduction

RSA-extending-wiener-attack

An implementation of RSA extending Wiener attack, which implements the general attack method of the following paper:

Nick Howgrave-Graham, Jean-Pierre Seifert: Extending Wiener's Attack in the Presence of Many Decrypting Exponents. CQRE 1999: 153-166

This paper is available in the following link:

https://www.sci-hub.ren/https://link.springer.com/chapter/10.1007/3-540-46701-7_14

This attack is feasible when there are many pairs (denoted the number of pairs as n) of RSA encryption exponents e_i and the corresponding small exponents d_i, which share the same modulus N.

This attack implementation is based on SageMath, and the attacking approach is based on lattice reduction.


Implementation Details

In Section 3.2 and Section 3.3 of the paper, it gave the exact form of the lattice construction where n=2 and n=3 respectively. However, for general cases, i.e., n>3, the paper implicitly gave a general approach in Section 3.1, and provided a more detailed illustration in Appendix. It mainly made use of Wiener's equations (denoted as W_i):

Wiener's equations

and Guo's equations (denoted as G_{i,j}):

Guo's equations

It generated the lattice via the multiplication of certain Wiener's equations and Guo's equations to construct the lattice. Moreover, we need to multiply the coefficients to balance the lattice, and then apply lattice reduction using the LLL or BKZ method.

After having reduced the lattice, we need to refer to Section 2.1 to find the r, and factor N by solving the quadratic equation with respect to p and q.

This repository implements the automatic generation of the equations (lattice), and can perform the attack when n<=6 at a reasonable cost of time and memory.


Usage

  • It can only run in SAGEMATH environment.
git clone https://github.com/X3NNY/RSA-extending-wiener-attack.git
cd ./RSA-extending-wiener-attack/
sage --pip install -r requirements.txt
sage rsa_extending_wiener_attack.sage

Example

Here is an example of the implementation.

example


The BibTeX of the original paper:

@inproceedings{Howgrave-GrahamS99,
  author    = {Nick Howgrave{-}Graham and
               Jean{-}Pierre Seifert},
  title     = {Extending Wiener's Attack in the Presence of Many Decrypting Exponents},
  booktitle = {{CQRE}},
  volume    = {1740},
  pages     = {153--166},
  year      = {1999},
}

rsa-extending-wiener-attack's People

Contributors

x3nny avatar zm-j avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar

Forkers

zm-j brandonros

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.