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:

May 2018

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