Kryptogram (RSA Public-Key Cipher)
- Type
- Education
- Category
- Cryptography demonstration — RSA in Atari BASIC
- Author
- L. Kolaříková (Atari version)
- Published in
- Adapted from LIST (Počítačové hry) No. 2; Atari version by L. Kolaříková, AK Rožnov, on the Czech disk magazine Flop, issue 5
- Language
- Atari BASIC
- Requirements
- Any 8-bit Atari with Atari BASIC
- Tags
- cryptography, rsa, mathematics, education, primes, czech, flop, atari-basic
About the program
This is real public-key cryptography in a few dozen lines of BASIC. The program uses the RSA scheme. Two primes, P = 107 and Q = 89, give the public modulus N = 9523. Each two-letter block of a message, written as a four-digit number, is encrypted by cubing it modulo N. Decryption raises the result to the secret power D, which is only easy to compute if you know P and Q. The REMs credit the Atari version to L. Kolaříková of Atari Klub Rožnov, upravila podle 2. čísla LIST (Počít. hry), "adapted from issue 2 of LIST (Computer Games)". It appeared on the Czech disk magazine Flop 5.
The Czech REMs and prompts
| Czech | English |
|---|---|
| KODOVACI program: ocekava text zpravy, vytiskne ciselnou formu, vytiskne kryptogram | Encoding: takes the message text, prints its numeric form, prints the cryptogram |
| DEKODOVACI program: ocekava kod kryptogramu, dekoduje blok… | Decoding: takes the cryptogram, decodes each block, prints the numbers and the whole message |
| KODOVACI KLIC: N=P*Q, P A Q jsou prvocisla | Encryption key N = P·Q, where P and Q are primes |
| DEKODOVACI KLIC: D=(2(P-1)(Q-1)+1)/3; P-1 MOD 3 nesmi byt 0 | Decryption key D = (2(P−1)(Q−1)+1)/3; P−1 and Q−1 must not be divisible by 3 |
| Kodovat? / Dekodovat? / Chces pokracovat? (A/N) | Encode? / Decode? / Continue? (A = yes) |
| Zprava k zakodovani / Zakodovany blok (konec=-1) / DEKODOVANA ZPRAVA | Message to encode / Encoded block (−1 to finish) / Decoded message |
| ZADEJ CISLO · JE PRVOCISLO (NE)VHODNE PRO KLIC · JE DELITELNE CISLEM | Enter a number · is a prime, (not) suitable for a key · is divisible by |
Typing it in
The listing is plain ASCII. The only special character is {CLEAR} in line 280, which is ESC followed by SHIFT-CLEAR.
How to use it
RUN, answer A to Kodovat?, and type a message in capitals, for example ATARI. The program prints each two-character block as a number (65·100+84 = 6584 for "AT"), then the cryptogram, one number per block. To decrypt, answer A to Dekodovat?, type the cryptogram numbers one by one and finish with -1. An odd-length message is padded with character 0, which comes back as a heart. For example, ATARI gives the blocks 6584, 6582 and 7300, and the cryptogram 8536, 9192, 2589.
GOTO 1000 runs the separate helper. Type a number and it tells you whether it's prime, and if so whether it suits this scheme (that is, whether P−1 is not divisible by 3). Use it to choose your own P and Q for line 240. Their product must stay above 9090 (the value of the block "ZZ") so that any two capital letters fit in a block.
How it works
- Encryption (lines 455–460): C = M³ mod N. It is done as two multiply-and-reduce steps, so the numbers never grow beyond about 9×10⁷, which Atari BASIC's 9–10 digit floating point holds exactly.
- Decryption (lines 510–535): computes C^D mod N by square-and-multiply, halving D each time round. With D = 6219, that takes 13 squarings instead of 6,218 multiplications.
- Why D works: 3·D = 2(P−1)(Q−1)+1, which is 1 more than a multiple of (P−1)(Q−1). By Euler's theorem, raising to the power 3·D therefore gives back the original block.
This toy key is far too small for real secrecy, since anyone can factor 9523. The mathematics, though, is exactly the same as in real RSA.
Listing
100 DIM A$(10),C$(10),M$(255),B$(10)
120 REM *****************************
125 REM * KODOVACI program: *
130 REM * ocekava text zpravy *
135 REM * vytiskne ciselnou formu *
140 REM * vytiskne kryptogram *
145 REM *****************************
150 REM * DEKODOVACI program: *
155 REM * ocekava kod kryptogramu *
160 REM * dekoduje blok *
165 REM * vytiskne ciselnou formu *
170 REM * vytiskne celou zpravu *
175 REM *****************************
180 REM * KODOVACI KLIC: N=P*Q *
185 REM * P A Q jsou prvocisla *
190 REM * DEKODOVACI KLIC: D *
195 REM * D=(2*(P-1)*(Q-1)+1)/3 *
200 REM * P-1 MOD 3 nesmi byt 0 *
205 REM * Q-1 MOD 3 nesmi byt 0 *
210 REM *****************************
211 REM * Pro ATARI upravila podle *
212 REM * 2.cisla LIST (Pocit. hry) *
213 REM * L.Kolarikova, AK Roznov *
214 REM *****************************
215 REM
220 DIM M(100):REM pocet bloku
225 CH=2:REM pocet znaku v bloku
230 REM
235 REM zvolena prvocisla P a Q
240 P=107:Q=89
245 REM
250 REM kodovaci klic N
255 N=P*Q
260 REM
265 REM dekodovaci klic D
270 D=(2*(P-1)*(Q-1)+1)/3
275 REM
280 PRINT "{CLEAR}"
285 PRINT "Kodovat?(A/N): ";
290 INPUT A$:IF A$(1)="A" THEN GOSUB 320
295 PRINT "Dekodovat?(A/N): ";
300 INPUT A$:IF A$="A" THEN GOSUB 470
305 PRINT "Chces pokracovat (A/N):";
310 INPUT A$:IF A$="A" THEN 280
315 END
320 REM
325 REM * KODOVACI RUTINA *
330 PRINT "Zprava k zakodovani:"
335 INPUT M$
340 IF M$="" THEN RETURN
345 L=LEN(M$)
350 O=INT(L/CH)
355 R=L-O*CH
360 IF R>0 THEN M$(L+1)=CHR$(0):GOTO 345
365 FOR I=0 TO O-1
370 M(I)=0
375 FOR J=1 TO CH
380 A=ASC(M$(2*I+J))
385 M(I)=M(I)*100
390 M(I)=M(I)+A
395 NEXT J
400 BL=M(I):GOSUB 540
405 NEXT I
410 PRINT:PRINT
415 PRINT "KRYPTOGRAM"
420 FOR I=0 TO O-1
425 M=M(I)
430 GOSUB 455
435 BL=C:GOSUB 540
440 NEXT I
445 PRINT
450 RETURN
455 C=M*M:C=C-INT(C/N)*N
460 C=C*M:C=C-INT(C/N)*N
465 RETURN
470 REM
475 REM * DEKODOVACI RUTINA *
480 I=0
485 PRINT "Zakodovany blok (konec=-1)"
487 INPUT C
490 IF C=-1 THEN 580
495 GOSUB 510
500 M(I)=M:I=I+1:PRINT M
505 GOTO 487
510 D1=D:M=1
515 IF D1/2=INT(D1/2) THEN 525
520 M=M*C:M=M-INT(M/N)*N
525 C=C*C:C=C-INT(C/N)*N
530 D1=INT(D1/2):IF D1>0 THEN 515
535 RETURN
540 REM
545 C$=STR$(BL)
550 IF LEN(C$)>=5 THEN 565
555 B$=C$:C$(1)=" ":C$(2)=B$
560 GOTO 550
565 PRINT C$
570 RETURN
575 REM
580 O=I-1:IF O=-1 THEN PRINT:RETURN
585 PRINT:PRINT "DEKODOVANA ZPRAVA:"
590 PRINT
595 FOR I=0 TO O
600 A$=STR$(M(I))
605 FOR J=1 TO CH
610 PRINT CHR$(VAL(A$(2*J-1,2*J)));
615 NEXT J:NEXT I:PRINT
620 RETURN
630 REM *****************************
890 REM *****************************
900 REM * NA RADKU 1000 ZACINA *
910 REM * RUTINA, KTERA ZKONTROLUJE,*
920 REM * ZDA ZADANE CISLO JE PRVO- *
930 REM * CISLO A ZDA JEHO PREDCHUD-*
940 REM * CE NENI DELITELNY TREMI. *
950 REM * DALSI PODMINKY JSOU UVEDE-*
960 REM * NY V POPISU KRYPTOGR.CAP. *
980 REM *****************************
1000 PRINT "ZADEJ CISLO:";
1010 INPUT C
1020 FOR I=2 TO C/2+1
1030 IF C/I=INT(C/I) THEN 1200
1040 NEXT I
1050 PRINT C;" JE PRVOCISLO ";
1060 IF (C-1)/3=INT((C-1)/3) THEN PRINT "NE";
1070 PRINT "VHODNE PRO KLIC"
1110 PRINT:PRINT:GOTO 1000
1200 PRINT C;" JE DELITELNE CISLEM ";I
1210 PRINT:PRINT:GOTO 1000
Credits
- Program listing: Kryptogram (RSA Public-Key Cipher) — program listing (Adapted from LIST (Počítačové hry) No. 2; Atari version by L. Kolaříková, AK Rožnov, on the Czech disk magazine Flop, issue 5) — L. Kolaříková (Atari version)
- Picture: A full round trip: ATARI becomes 8536 9192 2589 and decrypts back. The heart is the padding character. — L. Kolaříková (Atari version) (program); screenshot by the site
- Gury's Atari 8-bit Forever — Kryptogram — L. Kolaříková (Atari version)
