FilesExpand file tree

master

/

rsa_factorization.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

57 lines (48 loc) · 1.65 KB

master

/

rsa_factorization.py

Copy path

Top

File metadata and controls

• Code
• Blame

57 lines (48 loc) · 1.65 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

"""

An RSA prime factor algorithm.

The program can efficiently factor RSA prime number given the private key d and

public key e.

Source: on page 3 of https://crypto.stanford.edu/~dabo/papers/RSA-survey.pdf

More readable source: https://www.di-mgt.com.au/rsa_factorize_n.html

large number can take minutes to factor, therefore are not included in doctest.

"""

from __future__ import annotations

import math

import random

def rsafactor(d: int, e: int, n: int) -> list[int]:

"""

This function returns the factors of N, where p*q=N

Return: [p, q]

We call N the RSA modulus, e the encryption exponent, and d the decryption exponent.

The pair (N, e) is the public key. As its name suggests, it is public and is used to

encrypt messages.

The pair (N, d) is the secret key or private key and is known only to the recipient

of encrypted messages.

>>> rsafactor(3, 16971, 25777)

[149, 173]

>>> rsafactor(7331, 11, 27233)

[113, 241]

>>> rsafactor(4021, 13, 17711)

[89, 199]

"""

k = d * e - 1

p = 0

q = 0

while p == 0:

g = random.randint(2, n - 1)

t = k

while True:

if t % 2 == 0:

t = t // 2

x = (g**t) % n

y = math.gcd(x - 1, n)

if x > 1 and y > 1:

p = y

q = n // y

break # find the correct factors

else:

break # t is not divisible by 2, break and choose another g

return sorted([p, q])

if __name__ == "__main__":

import doctest

doctest.testmod()