exploit the possibilities

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:

February 2019

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

Top Authors In Last 30 Days

File Tags

Systems

packet storm

© 2019 Packet Storm. All rights reserved.

Services
Security Services
Hosting By
Rokasec
close