**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 | View

`#!/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;

}

Login or Register to add favorites

- ActiveX (928)
- Advisory (74,943)
- Arbitrary (14,616)
- BBS (2,859)
- Bypass (1,439)
- CGI (1,004)
- Code Execution (6,039)
- Conference (657)
- Cracker (784)
- CSRF (3,198)
- DoS (20,992)
- Encryption (2,303)
- Exploit (47,618)
- File Inclusion (4,087)
- File Upload (909)
- Firewall (821)
- Info Disclosure (2,492)
- Intrusion Detection (827)
- Java (2,622)
- JavaScript (763)
- Kernel (5,646)
- Local (13,721)
- Magazine (584)
- Overflow (11,693)
- Perl (1,402)
- PHP (4,971)
- Proof of Concept (2,241)
- Protocol (3,099)
- Python (1,313)
- Remote (28,665)
- Root (3,378)
- Ruby (549)
- Scanner (1,614)
- Security Tool (7,487)
- Shell (2,898)
- Shellcode (1,180)
- Sniffer (868)
- Spoof (2,000)
- SQL Injection (15,646)
- TCP (2,329)
- Trojan (616)
- UDP (860)
- Virus (647)
- Vulnerability (29,438)
- Web (8,628)
- Whitepaper (3,633)
- x86 (928)
- XSS (16,910)
- Other

- AIX (421)
- Apple (1,781)
- BSD (368)
- CentOS (52)
- Cisco (1,904)
- Debian (5,945)
- Fedora (1,688)
- FreeBSD (1,241)
- Gentoo (4,044)
- HPUX (873)
- iOS (288)
- iPhone (108)
- IRIX (220)
- Juniper (67)
- Linux (39,740)
- Mac OS X (675)
- Mandriva (3,105)
- NetBSD (255)
- OpenBSD (474)
- RedHat (9,889)
- Slackware (941)
- Solaris (1,598)
- SUSE (1,444)
- Ubuntu (7,201)
- UNIX (8,875)
- UnixWare (180)
- Windows (5,897)
- Other

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

- Services
- Security Services
- Hosting By
- Rokasec