Twenty Year Anniversary

RSA Factorization Attack Using Fermat's Algorithm

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.

tags | tool, cracker
MD5 | 1c37da73d3f7d27402cfcfb57295c95c

RSA Factorization Attack Using Fermat's Algorithm

Change Mirror Download
#!/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;
}

Comments

RSS Feed Subscribe to this comment feed

No comments yet, be the first!

Login or Register to post a comment

File Archive:

October 2018

  • Su
  • Mo
  • Tu
  • We
  • Th
  • Fr
  • Sa
  • 1
    Oct 1st
    26 Files
  • 2
    Oct 2nd
    15 Files
  • 3
    Oct 3rd
    15 Files
  • 4
    Oct 4th
    15 Files
  • 5
    Oct 5th
    15 Files
  • 6
    Oct 6th
    2 Files
  • 7
    Oct 7th
    3 Files
  • 8
    Oct 8th
    23 Files
  • 9
    Oct 9th
    16 Files
  • 10
    Oct 10th
    15 Files
  • 11
    Oct 11th
    19 Files
  • 12
    Oct 12th
    16 Files
  • 13
    Oct 13th
    2 Files
  • 14
    Oct 14th
    2 Files
  • 15
    Oct 15th
    15 Files
  • 16
    Oct 16th
    20 Files
  • 17
    Oct 17th
    0 Files
  • 18
    Oct 18th
    0 Files
  • 19
    Oct 19th
    0 Files
  • 20
    Oct 20th
    0 Files
  • 21
    Oct 21st
    0 Files
  • 22
    Oct 22nd
    0 Files
  • 23
    Oct 23rd
    0 Files
  • 24
    Oct 24th
    0 Files
  • 25
    Oct 25th
    0 Files
  • 26
    Oct 26th
    0 Files
  • 27
    Oct 27th
    0 Files
  • 28
    Oct 28th
    0 Files
  • 29
    Oct 29th
    0 Files
  • 30
    Oct 30th
    0 Files
  • 31
    Oct 31st
    0 Files

Top Authors In Last 30 Days

File Tags

Systems

packet storm

© 2018 Packet Storm. All rights reserved.

Services
Security Services
Hosting By
Rokasec
close