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