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

Want To Donate?


Bitcoin: 18PFeCVLwpmaBuQqd5xAYZ8bZdvbyEWMmU

File Archive:

August 2018

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