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

}

Bitcoin:

- ActiveX (927)
- Advisory (68,705)
- Arbitrary (13,167)
- BBS (2,859)
- Bypass (1,144)
- CGI (963)
- Code Execution (4,950)
- Conference (610)
- Cracker (769)
- CSRF (2,901)
- DoS (18,820)
- Encryption (2,244)
- Exploit (41,557)
- File Inclusion (3,904)
- File Upload (791)
- Firewall (812)
- Info Disclosure (2,081)
- Intrusion Detection (750)
- Java (2,233)
- JavaScript (663)
- Kernel (4,762)
- Local (12,948)
- Magazine (567)
- Overflow (10,509)
- Perl (1,354)
- PHP (4,714)
- Proof of Concept (1,986)
- Protocol (2,688)
- Python (1,079)
- Remote (25,960)
- Root (3,094)
- Scanner (1,518)
- Security Tool (6,940)
- Shell (2,630)
- Shellcode (1,011)
- Sniffer (839)
- Spoof (1,902)
- SQL Injection (14,648)
- TCP (2,222)
- Trojan (553)
- UDP (848)
- Virus (614)
- Vulnerability (26,935)
- Web (7,583)
- Whitepaper (3,378)
- x86 (808)
- XSS (15,574)
- Other

- AIX (409)
- Apple (1,569)
- BSD (337)
- Cisco (1,818)
- Debian (5,569)
- Fedora (1,683)
- FreeBSD (1,197)
- Gentoo (3,590)
- HPUX (865)
- iOS (178)
- iPhone (103)
- IRIX (219)
- Juniper (66)
- Linux (33,846)
- Mac OS X (653)
- Mandriva (3,105)
- NetBSD (255)
- OpenBSD (456)
- RedHat (6,684)
- Slackware (844)
- Solaris (1,570)
- SUSE (1,444)
- Ubuntu (5,749)
- UNIX (8,315)
- UnixWare (172)
- Windows (5,365)
- 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!