· 7 years ago · Jan 22, 2019, 01:20 PM
1#!/usr/bin/perl
2#
3# RSA Factorization Attack using Fermat's algorithm
4# (Simple Turing machine)
5#
6# Copyright 2018 (c) Todor Donev
7# <todor.donev at gmail.com>
8# https://ethical-hacker.org/
9# https://fb.com/ethicalhackerorg
10#
11# RSA Factorization Attack:
12# The security of RSA is based on the idea that the modulus
13# is so large that is infeasible to factor it in reasonable time.
14# Bob selects P and Q and calculate N=PAQ. Although N is public,
15# P and Q are secret. If Eve can factor N and obtain P and Q,
16# Eve then can calculate d = e-1mod I(N) because e is public.
17# The private exponent d is the trapdoor that Eve uses to decrypt
18# any encrypted message. The factorization attack is a
19# extremely giant dispute for security of RSA algorithm.
20# Some existing factorization algorithms can be generating
21# public and private key of RSA algorithm, by factorization
22# of modulus N. But they are taking huge time for factorization of
23# N, in case of P and Q very large. We are focusing on
24# factorization speed and proposing new factorization method
25# to enhance the speed of factorization. Related works for
26# factorization of modulus N are following
27#
28# For now, Factoring the public key is seen as the best way to go
29# about cracking RSA.
30#
31# See also:
32# https://en.wikipedia.org/wiki/Fermat%27s_Last_Theorem
33# https://en.wikipedia.org/wiki/Turing_machine
34#
35# Install Lib GMP on CentOS:
36# sudo yum install gmp-devel
37#
38# Install Lib GMP on Ubuntu:
39# sudo apt-get install libgmp-dev
40#
41# cpan install Math::Prime::Util
42# cpan install Math::BigInt::GMP
43# cpan install Math::BigInt
44# cpan install ntheory
45# cpan install bigint
46#
47# USAGE:
48# [todor@paladium ~]$ perl fermat.pl
49# Usage: fermat.pl <number (base 10)>
50# [todor@paladium ~]$ perl fermat.pl 313337
51# [+] RSA Factorization Attack using Fermat's algorithm
52# [+] Author: Todor Donev - todor.donev@gmail.com
53# [+] https://ethical-hacker.org/
54# [+] https://fb.com/ethicalhackerorg
55# [=] ==========================================
56# [+] Size of the number: 6 digits
57# [+] Number for factorization: 313337
58# [+] Factoring..
59# [+] p = 727
60# [+] q = 431
61# [+] p*q = 313337
62# [=] ==========================================
63# [+] Good night, sweet prince.. :)))
64# [todor@paladium ~]$ perl fermat.pl 3133337
65# [+] RSA Factorization Attack using Fermat's algorithm
66# [+] Author: Todor Donev - todor.donev@gmail.com
67# [+] https://ethical-hacker.org/
68# [+] https://fb.com/ethicalhackerorg
69# [=] ==========================================
70# [+] Size of the number: 7 digits
71# [+] Number for factorization: 3133337
72# [+] Factoring..
73# [+] 3133337 is Prime
74# [=] ==========================================
75# [+] Good night, sweet prince.. :)))
76# [todor@paladium ~]$
77#
78# Disclaimer:
79# This or previous programs is for Educational
80# purpose ONLY. Do not use it without permission.
81# The usual disclaimer applies, especially the
82# fact that Todor Donev is not liable for any
83# damages caused by direct or indirect use of the
84# information or functionality provided by these
85# programs. The author or any Internet provider
86# bears NO responsibility for content or misuse
87# of these programs or any derivatives thereof.
88# By using these programs you accept the fact
89# that any damage (dataloss, system crash,
90# system compromise, etc.) caused by the use
91# of these programs is not Todor Donev's
92# responsibility.
93#
94# Use them at your own risk!
95
96use strict;
97use warnings;
98use ntheory qw(sqrtint is_prime is_power);
99use bigint;
100
101my $number = $ARGV[0];
102die "Usage: $0 <number (base 10)>\n" if(@ARGV != 1);
103printf("[+] RSA Factorization Attack using Fermat's algorithm\n");
104printf("[+] Author: Todor Donev - todor.donev\@gmail.com\n");
105printf("[+] https://ethical-hacker.org/\n");
106printf("[+] https://fb.com/ethicalhackerorg\n");
107printf("[=] ==========================================\n");
108printf("[+] Size of the number: %s digits\n",length($number));
109printf("[+] Number for factorization: %s\n", $number);
110printf("[+] Factorization..\n");
111fermat($number);
112bye("[+] Good night, sweet prince.. :)))\n");
113sub fermat{
114 my ($n) = @_;
115 if ($n <= 1){
116 printf("[+] %s <= 1\n", $n);
117 return $n;
118 }
119 elsif (is_prime($n)) {
120 printf("[+] %s is Prime\n", $n);
121 return $n;
122 }
123 $n <<= 2;
124 my $p = sqrtint($n);
125 my $q = $p * $p - $n;
126 until (is_power($q, 2)) {
127 $q += 2 * $p++ + 1;
128 }
129 my $s = sqrtint($q);
130 my ($x1, $x2) = (
131 ($p + $s) >> 1,
132 ($p - $s) >> 1,
133 );
134 return sort{$a<=>$b}(
135 printf("[+] p = %s\n", $x1),
136 printf("[+] q = %s\n", $x2),
137 printf("[+] p*q = %s\n", $x1*$x2)
138 );
139}
140sub bye{
141 my $msg = shift;
142 printf("[=] ==========================================\n");
143 printf($msg);
144 exit;
145}