Post Reply 
(42S) RSA En- & De-cryption, Everything You Need
05-26-2015, 04:18 PM (This post was last modified: 06-15-2017 01:49 PM by Gene.)
Post: #1
(42S) RSA En- & De-cryption, Everything You Need
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
Find all posts by this user
Quote this message in a reply
Post Reply 




User(s) browsing this thread: 1 Guest(s)