cryptRSA/Fbreak.cpp at master · inascim/cryptRSA · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <stdlib.h>
#include <stdio.h>
#include <math.h>


unsigned long long
mod(unsigned long long a1, unsigned long long b1){

	long long r1 = a1 % b1;

    /* Uma correçã é necessária se r e b não forem do mesmo sinal */

    /* se r for negativo e b positivo, precisa corrigir */
	if ((r1 < 0) && (b1 > 0))
		return (b1 + r1);

    /* Se ra for positivo e b negativo, nova correcao */
	if ((r1 > 0) && (b1 < 0))
		return (b1 + r1);

	return (r1);
}

unsigned long long
euclides_ext(unsigned long long a, unsigned long long b, unsigned long long c){

	unsigned long long r;

	r = mod(b, a);

	if (r == 0) {
		return (mod((c / a), (b / a)));   // retorna (c/a) % (b/a)
	}

	return ((euclides_ext(r, a, -1*c) * b + c) / (mod(a, b)));
}
int
main(){

	long long n = 10142789312725007;

	unsigned long long d;

	unsigned long long i;

	for( i  = pow( n, 0.5); i > 3; i-=2)
		if (n%i == 0)
		{
			printf("P: %llu \n\n",i);
			printf("Q: %llu \n\n",n/i);
			break;
		}

	unsigned long long qq = ( i - 1 ) * (n/i - 1);


	d = euclides_ext(5, qq, 1);

	printf("D: %llu \n\n",d);

	return 0;
}


/*
for i in xrange(int(p**0.5+2), 3, -2):
    if p%i == 0:
        print i
        print p/i
        break


*/


/*
void
rsa_break(unsigned long long p, unsigned long long q, unsigned long long e){

	p, q, e = argv[1:]
	p=int(p)
	q=int(q)
	e=int(e)

	n = p * q

	qq = (p – 1) * (q – 1)

	d = euclides_ext(e, qq, 1)
	print "N =", n
	print "QQ =", qq
	print "D =", d
}*/