+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Software Libraries (/forum-10.html)
+--- Forum: General Software Library (/forum-13.html)
+--- Thread: (42S) RSA En- & De-cryption, Everything You Need (/thread-3980.html)
(42S) RSA En- & De-cryption, Everything You Need - Gerald H - 05-26-2015 04:18 PM
RSA encryption takes a positive integer A & finds for encryption exponent e A^e mod n, the encrypted value.
Decryption finds for decryption exponent d (A^e mod n)^d mod n, the decrypted value, ie A.
Normally e & n are made public, d remains secret.
RSAST sets the parameters n, e & d given an integer starting value S < 7 to determine the size of the two prime factors of n, p & q.
→RSA encrypts the X-register into the X-register.
RSA→ decrypts as above.
For the sub-programmes see in the code box.
Code:
0. { 128-Byte Prgm }
1. LBL “RSAST”
2. STO “p”
3. XEQ “PFOR”
4. X<> “p”
5. XEQ “PFOR”
6. STO “q”
7. RCL* “p”
8. STO “n”
9. RCL- ST L
10. RCL- “p”
11. 1
12. +
13. STO “phi”
14. SQRT
15. RAN
16. *
17. IP
18. RCL ST X
19. 2
20. MOD
21. 1
22. +
23. –
24. STO “e”
25. LBL 00
26. 2
27. RCL+ “e”
28. STO “e”
29. RCL “phi”
30. XEQ “INVM”
31. X=0?
32. GTO 00
33. STO “d”
34. RTN
35. LBL “→RSA”
36. RCL “e”
37. GTO 01
38. LBL “RSA→”
39. RCL “d”
40. LBL 01
41. RCL “n”
42. XEQ “MOD↑”
43. END
For positive integer input n PFOR returns a prime integer of length n.
0. { 32-Byte Prgm }
1. LBL “PFOR”
2. XEQ “RAN#”
3. 1E12
4. 11
5. –
6. X<=Y?
7. RTN
8. R↓
9. GTO “PRI↑”
10. END
RAN# returns a random integer of input size.
0. { 13-Byte Prgm }
1. LBL “RAN#”
2. 10^X
3. RAN
4. *
5. IP
6. END
PRI↑for integer input returns the least greater prime number.
0. { 43-Byte Prgm }
1. LBL “↓PRI”
2. +/-
3. LBL “PRI↑”
4. IP
5. STO ST Y
6. 2
7. MOD
8. +
9. STO 06
10. DSE 06
11. LBL 00
12. 2
13. STO+ 06
14. RCL 06
15. XEQ “?PRI”
16. X=0?
17. GTO 00
18. R↓
19. END
?PRI returns 1 or 0 as input is prime or composite.
0. { 42-Byte Prgm }
1. LBL “?PRI”
2. ABS
3. XEQ “SMAF”
4. X=0?
5. GTO 00
6. RCL 01
7. 16637 = 127 * 131
8. X>Y?
9. GTO 01
10. R↓
11. XEQ “RABM”
12. GTO 00
13. LBL 01
14. SIGN
15. LBL 00
16. RCL 01
17. X<>Y
18. END
SMAF tests for factors up to 113.
0. { 51-Byte Prgm }
1. LBL “SMAF”
2. STO 01
3. 3
4. X>=Y?
5. GTO 01
6. DSE ST X
7. MOD
8. X=0?
9. RTN
10. RCL 01
11. SQRT
12. FP
13. X=0?
14. RTN
15. LASTX
16. IP
17. 113
18. X>Y?
19. X<>Y
20. 1
21. LBL 00
22. 2
23. +
24. RCL 01
25. RCL ST Y
26. MOD
27. X=0?
28. RTN
29. R↓
30. X<Y?
31. GTO 00
32. LBL 01
33. SIGN
34. END
For positive integer input RABM carries out one strong pseudo-prime test to a random base.
0. { 112-Byte Prgm }
1. LBL “RABM”
2. STO ST Y
3. 3
4. –
5. RAN
6. *
7. IP
8. 2
9. +
10. LBL “?SPS”
11. STO 05
12. R↓
13. +/-
14. STO 00
15. +/-
16. STO 01
17. –1
18. X<>Y
19. RCL+ ST Y
20. 0
21. LBL 00
22. R↓
23. 2
24. /
25. ISG ST Y
26. CLA
27. RCL ST X
28. LAST X
29. MOD
30. X=0?
31. GTO 00
32. CLX
33. RCL ST Z
34. X<> 05
35. X<>Y
36. XEQ “M↑”
37. 1
38. X=Y?
39. RTN
40. +/-
41. RCL+ 01
42. X=Y?
43. GTO 01
44. RCL 05
45. X=0?
46. RTN
47. RCL ST Z
48. LBL 02
49. XEQ “SQM”
50. 1
51. X=Y?
52. GTO 03
53. +/-
54. RCL+ 01
55. X=Y?
56. GTO 01
57. R↓
58. DSE 05
59. GTO 02
60. LBL 03
61. CLX
62. RTN
63. LBL 01
64. SIGN
65. END
INVM finds the multiplicative inverse of stack level Y modulo stack level X.
0. { 26-Byte Prgm }
1. LBL “INVM”
2. XEQ “BEZO”
3. RCL ST Z
4. DSE ST X
5. GTO 00
6. RCL 05
7. RCL 08
8. MOD
9. RTN
10. LBL 00
11. CLX
12. END
For integer input Y & X BEZO returns
gcd(X,Y)
a ib
X iY
where a & b are the multiplicative inverses of X & Y modulo Y & X.
0. { 75-Byte Prgm }
1. LBL “BEZO”
2. STO 08
3. 1
4. COMPLEX
5. X<>Y
6. STO 07
7. 0
8. COMPLEX
9. LBL 00
10. ENTER
11. COMPLEX
12. R↓
13. X=0?
14. GTO 01
15. RCL ST Z
16. X<>Y
17. /
18. COMPLEX
19. R↓
20. IP
21. RCL* ST Y
22. RCL- ST Z
23. +/-
24. GTO 00
25. LBL 01
26. RCL ST Z
27. COMPLEX
28. RCL ST Y
29. RCL ST Y
30. RCL* 08
31. –
32. RCL/ 07
33. STO 05
34. COMPLEX
35. RCL ST Y
36. SIGN
37. STO* 05
38. STO* ST Z
39. *
40. RCL 08
41. RCL 07
42. COMPLEX
43. END
M* returns the product of X- & Y-registers modulo register 01
0. { 77-Byte Prgm }
1. LBL “M/”
2. X<>Y
3. STO 02
4. R↓
5. RCL 01
6. XEQ “INVM”
7. X=0?
8. RTN
9. RCL 02
10. LBL “M*”
11. RCL ST X
12. 1E6
13. MOD
14. X<>Y
15. RCL- ST Y
16. COMPLEX
17. X<>Y
18. 1E6
19. MOD
20. RCL ST Z
21. RCL- ST Y
22. RCL* ST Z
23. X<>Y
24. RCL* ST Z
25. COMPLEX
26. RCL 00
27. MOD
28. +
29. RCL 01
30. MOD
31. X<>Y
32. COMPLEX
33. RCL 00
34. MOD
35. X<>Y
36. RCL 01
37. MOD
38. +
39. RCL 00
40. MOD
41. +
42. RCL 01
43. MOD
44. END
SQM returns the square of X-register modulo register 01.
0. { 42-Byte Prgm }
1. LBL “SQM”
2. STO ST Y
3. 1E6
4. MOD
5. STO ST Z
6. –
7. ENTER
8. X^2
9. RCL 00
10. MOD
11. X<>Y
12. R↑
13. STO* ST T
14. *
15. RCL 01
16. MOD
17. RCL- ST L
18. RCL+ ST L
19. RCL 01
20. MOD
21. +
22. RCL 00
23. MOD
24. +
25. RCL 01
26. MOD
27. END
M↑ returns Y ^ X modulo register 01.
0. { 60-Byte Prgm }
1. LBL “MOD↑”
2. STO 01
3. +/-
4. STO 00
5. R↓
6. LBL “M↑”
7. STO 02
8. R↓
9. STO 03
10. SIGN
11. GTO 00
12. LBL 01
13. 2
14. MOD
15. X≠0?
16. GTO 02
17. LASTX
18. STO/ 02
19. RCL 03
20. XEQ “SQM”
21. STO 03
22. RCL 02
23. GTO 01
24. LBL 02
25. STO- 02
26. RCL 04
27. RCL 03
28. XEQ “M*”
29. LBL 00
30. STO 04
31. RCL 02
32. X≠0?
33. GTO 01
34. R↓
35. END