**RSA Factorization Attack Using Fermat's Algorithm**- Posted Apr 5, 2018
- Authored by Todor Donev
Script that performs RSA factorization attack using Fermat's algorithm.

- MD5 |
`1c37da73d3f7d27402cfcfb57295c95c`

- Download | Favorite | Comments (0)

`#!/usr/bin/perl`

#

# RSA Factorization Attack using Fermat's algorithm

# (Simple Turing machine)

#

# Copyright 2018 (c) Todor Donev

# <todor.donev at gmail.com>

# https://ethical-hacker.org/

# https://fb.com/ethicalhackerorg

#

# RSA Factorization Attack:

# The security of RSA is based on the idea that the modulus

# is so large that is infeasible to factor it in reasonable time.

# Bob selects P and Q and calculate N=PAQ. Although N is public,

# P and Q are secret. If Eve can factor N and obtain P and Q,

# Eve then can calculate d = e-1mod I(N) because e is public.

# The private exponent d is the trapdoor that Eve uses to decrypt

# any encrypted message. The factorization attack is a

# extremely giant dispute for security of RSA algorithm.

# Some existing factorization algorithms can be generating

# public and private key of RSA algorithm, by factorization

# of modulus N. But they are taking huge time for factorization of

# N, in case of P and Q very large. We are focusing on

# factorization speed and proposing new factorization method

# to enhance the speed of factorization. Related works for

# factorization of modulus N are following

#

# For now, Factoring the public key is seen as the best way to go

# about cracking RSA.

#

# See also:

# https://en.wikipedia.org/wiki/Fermat%27s_Last_Theorem

# https://en.wikipedia.org/wiki/Turing_machine

#

# Install Lib GMP on CentOS:

# sudo yum install gmp-devel

#

# Install Lib GMP on Ubuntu:

# sudo apt-get install libgmp-dev

#

# cpan install Math::Prime::Util

# cpan install Math::BigInt::GMP

# cpan install Math::BigInt

# cpan install ntheory

# cpan install bigint

#

# USAGE:

# [todor@paladium ~]$ perl fermat.pl

# Usage: fermat.pl <number (base 10)>

# [todor@paladium ~]$ perl fermat.pl 313337

# [+] RSA Factorization Attack using Fermat's algorithm

# [+] Author: Todor Donev - todor.donev@gmail.com

# [+] https://ethical-hacker.org/

# [+] https://fb.com/ethicalhackerorg

# [=] ==========================================

# [+] Size of the number: 6 digits

# [+] Number for factorization: 313337

# [+] Factoring..

# [+] p = 727

# [+] q = 431

# [+] p*q = 313337

# [=] ==========================================

# [+] Good night, sweet prince.. :)))

# [todor@paladium ~]$ perl fermat.pl 3133337

# [+] RSA Factorization Attack using Fermat's algorithm

# [+] Author: Todor Donev - todor.donev@gmail.com

# [+] https://ethical-hacker.org/

# [+] https://fb.com/ethicalhackerorg

# [=] ==========================================

# [+] Size of the number: 7 digits

# [+] Number for factorization: 3133337

# [+] Factoring..

# [+] 3133337 is Prime

# [=] ==========================================

# [+] Good night, sweet prince.. :)))

# [todor@paladium ~]$

#

# Disclaimer:

# This or previous programs is for Educational

# purpose ONLY. Do not use it without permission.

# The usual disclaimer applies, especially the

# fact that Todor Donev is not liable for any

# damages caused by direct or indirect use of the

# information or functionality provided by these

# programs. The author or any Internet provider

# bears NO responsibility for content or misuse

# of these programs or any derivatives thereof.

# By using these programs you accept the fact

# that any damage (dataloss, system crash,

# system compromise, etc.) caused by the use

# of these programs is not Todor Donev's

# responsibility.

#

# Use them at your own risk!

use strict;

use warnings;

use ntheory qw(sqrtint is_prime is_power);

use bigint;

my $number = $ARGV[0];

die "Usage: $0 <number (base 10)>\n" if(@ARGV != 1);

printf("[+] RSA Factorization Attack using Fermat's algorithm\n");

printf("[+] Author: Todor Donev - todor.donev\@gmail.com\n");

printf("[+] https://ethical-hacker.org/\n");

printf("[+] https://fb.com/ethicalhackerorg\n");

printf("[=] ==========================================\n");

printf("[+] Size of the number: %s digits\n",length($number));

printf("[+] Number for factorization: %s\n", $number);

printf("[+] Factorization..\n");

fermat($number);

bye("[+] Good night, sweet prince.. :)))\n");

sub fermat{

my ($n) = @_;

if ($n <= 1){

printf("[+] %s <= 1\n", $n);

return $n;

}

elsif (is_prime($n)) {

printf("[+] %s is Prime\n", $n);

return $n;

}

$n <<= 2;

my $p = sqrtint($n);

my $q = $p * $p - $n;

until (is_power($q, 2)) {

$q += 2 * $p++ + 1;

}

my $s = sqrtint($q);

my ($x1, $x2) = (

($p + $s) >> 1,

($p - $s) >> 1,

);

return sort{$a<=>$b}(

printf("[+] p = %s\n", $x1),

printf("[+] q = %s\n", $x2),

printf("[+] p*q = %s\n", $x1*$x2)

);

}

sub bye{

my $msg = shift;

printf("[=] ==========================================\n");

printf($msg);

exit;

}

- ActiveX (928)
- Advisory (69,732)
- Arbitrary (13,453)
- BBS (2,859)
- Bypass (1,220)
- CGI (969)
- Code Execution (5,145)
- Conference (627)
- Cracker (773)
- CSRF (2,976)
- DoS (19,348)
- Encryption (2,258)
- Exploit (43,129)
- File Inclusion (3,943)
- File Upload (815)
- Firewall (815)
- Info Disclosure (2,287)
- Intrusion Detection (765)
- Java (2,298)
- JavaScript (681)
- Kernel (4,922)
- Local (13,119)
- Magazine (570)
- Overflow (10,711)
- Perl (1,368)
- PHP (4,755)
- Proof of Concept (2,051)
- Protocol (2,747)
- Python (1,101)
- Remote (26,615)
- Root (3,135)
- Ruby (501)
- Scanner (1,530)
- Security Tool (7,042)
- Shell (2,701)
- Shellcode (1,054)
- Sniffer (844)
- Spoof (1,916)
- SQL Injection (15,010)
- TCP (2,242)
- Trojan (554)
- UDP (850)
- Virus (618)
- Vulnerability (27,423)
- Web (7,753)
- Whitepaper (3,421)
- x86 (843)
- XSS (15,834)
- Other

- AIX (413)
- Apple (1,619)
- BSD (343)
- Cisco (1,839)
- Debian (5,693)
- Fedora (1,684)
- FreeBSD (1,206)
- Gentoo (3,639)
- HPUX (868)
- iOS (205)
- iPhone (104)
- IRIX (219)
- Juniper (67)
- Linux (34,739)
- Mac OS X (656)
- Mandriva (3,105)
- NetBSD (255)
- OpenBSD (459)
- RedHat (7,043)
- Slackware (881)
- Solaris (1,579)
- SUSE (1,444)
- Ubuntu (5,993)
- UNIX (8,408)
- UnixWare (175)
- Windows (5,439)
- Other

- Site Links
- News by Month
- News Tags
- Files by Month
- File Tags
- File Directory

- Services
- Security Services
- Hosting By
- Rokasec

## Comments

Subscribe to this comment feedNo comments yet, be the first!