**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 (927)
- Advisory (69,081)
- Arbitrary (13,250)
- BBS (2,859)
- Bypass (1,166)
- CGI (966)
- Code Execution (5,024)
- Conference (617)
- Cracker (769)
- CSRF (2,918)
- DoS (19,022)
- Encryption (2,249)
- Exploit (42,028)
- File Inclusion (3,918)
- File Upload (796)
- Firewall (812)
- Info Disclosure (2,103)
- Intrusion Detection (754)
- Java (2,263)
- JavaScript (667)
- Kernel (4,830)
- Local (13,004)
- Magazine (569)
- Overflow (10,580)
- Perl (1,359)
- PHP (4,724)
- Proof of Concept (2,008)
- Protocol (2,706)
- Python (1,082)
- Remote (26,127)
- Root (3,107)
- Scanner (1,525)
- Security Tool (6,976)
- Shell (2,641)
- Shellcode (1,032)
- Sniffer (841)
- Spoof (1,906)
- SQL Injection (14,725)
- TCP (2,231)
- Trojan (553)
- UDP (849)
- Virus (615)
- Vulnerability (27,088)
- Web (7,644)
- Whitepaper (3,401)
- x86 (822)
- XSS (15,667)
- Other

- AIX (411)
- Apple (1,584)
- BSD (341)
- Cisco (1,826)
- Debian (5,617)
- Fedora (1,683)
- FreeBSD (1,201)
- Gentoo (3,598)
- HPUX (867)
- iOS (185)
- iPhone (104)
- IRIX (219)
- Juniper (66)
- Linux (34,166)
- Mac OS X (653)
- Mandriva (3,105)
- NetBSD (255)
- OpenBSD (457)
- RedHat (6,811)
- Slackware (858)
- Solaris (1,575)
- SUSE (1,444)
- Ubuntu (5,838)
- UNIX (8,349)
- UnixWare (174)
- Windows (5,385)
- 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!