RSA Principle 3

Posted on | Edited on | In

RSA’s Reliability

In principle 2 total 6 number appear

1
2
3
4
5
6
p     53
　　q     271
　　n     14363
　　φ(n)  14040
　　e     97
　　d     9553

Public key use 2 of them, n and e.
The rest of them do not public. The most important number above
is d, because n and d compose to private key.

Discuss

How to compute d, only know n and e

  1. $ed \equiv 1 \quad (mod \quad \phi(n))$
    Only know e and than know what d is,
    among them, e is public.

  2. $\phi(n) = (p-1) \times (q-1)$
    Need know what p and q is.

  3. $n = p \times q$
    Only n factorization, than got what p q probaly is.

Conclusion: If number n could be factorization, than
d [mod inverse element] could be found.
That mean private key be hacked.

Think

Extremely large number’s mod inverse element possible is extremely large as well. The difficulty in factorizing two coprime number that the mod inverse element possible number mod by public key e rest got 1, the more difficulty it is, the more security key is.

Human’s power only solve number factorization max to 232 in decimal, 768 in binary.
So at present, 768 bits[96 bytes] is the longest RSA key length be breaked.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
12301866845301177551304949
　　58384962720772853569595334
　　79219732245215172640050726
　　36575187452021997864693899
　　56474942774063845925192557
　　32630345373154826850791702
　　61221429134616704292143116
　　02221240479274737794080665
　　351419597459856902143413
   =
33478071698956898786044169
　　84821269081770479498371376
　　85689124313889828837938780
　　02287614711652531743087737
　　814467999489
　　　　×
　　36746043666799590428244633
　　79962795263227915816434308
　　76426760322838157396665112
　　79233373417143396810270092
　　798736308917