exploit the possibilities
Home Files News &[SERVICES_TAB]About Contact Add New

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
SHA-256 | c6570807c86958d016e3357f7faa38b91231b7b1400248e719fb87d055b6bc72

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;
}
Login or Register to add favorites

File Archive:

March 2024

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

Top Authors In Last 30 Days

File Tags

Systems

packet storm

© 2022 Packet Storm. All rights reserved.

Services
Security Services
Hosting By
Rokasec
close