Category : BASIC Source Code
Archive   : PKSCRYPT.ZIP
Filename : CRACKER.BAS

10 REM program to crack the PKSCrypt secret key knowing the public key
20 REM written by lloyd miller and based on Richard B. Leining's "Hyper"
30 REM
40 REM the maximum key length that this program will work properly with is
50 REM about 8 digits
60 REM
70 DEFDBL A-Z
80 REM
90 REM program HYPER
100 REM by Richard B. Leining
110 REM (From Byte magazine, March 1985, page 396)
120 REM
130 PRINT "Hyper factors or tests prime by intersecting"
140 PRINT "twin hyperbolas x*y = n and (x-1)*(y-1) = fe"
150 REM read n and (d or e) from a key file
160 INPUT "keyfile to decode"; KF$
170 OPEN KF$ FOR INPUT AS #1
180 LINE INPUT #1, N$
190 PRINT N$
200 IF LEFT$(N$, 4) <> "n = " THEN 250
210 LINE INPUT #1, E$
220 PRINT E$
230 IF LEFT$(E$, 4) = "e = " THEN 280
240 IF LEFT$(E$, 4) = "d = " THEN 280
250 PRINT "not a key file"
260 CLOSE 1
270 GOTO 160
280 N = VAL(MID$(N$, 5))
290 CLOSE 1
300 REM tolerance serves as zero in tests
310 TOL = .0001#
320 REM calc consts a and b, scaled down to defer overflow
330 A = (N + 1) / 2
340 B = (N - 1) / 2
350 B = B * B
360 REM find critical value of fe/4 for two real intersections
370 FECR4 = (A - ROOT) / 2
380 FECR4 = INT(FECR4)
390 REM estimate lowwer bound of fe
400 MIN% = 3
410 FEMN4 = A / 2 - (MIN% + N / MIN%) / 4
420 FEMN4 = INT(FEMN4)
430 REM predict max reasonable trials for fe
440 MAX = 1 + FECR4 - FEMN4
450 PRINT "max reasonable trials = ";INT(MAX)
460 ALLOW = INT(MAX)
470 REM upper bound is sometimes a solution for fe. try it fisrt
480 FE4 = FECR4
490 TRIAL = 1
500 REM calc polynomial z (r ^ 2) which is scaled by 1/4
510 Z = B - FE4 * (A - FE4) * 4
520 IF Z < 0# THEN 580
530 REM select perfect square that makes x, y integers
540 ROOT = SQR(Z)
550 RDEC = ROOT - INT(ROOT)
560 IF RDEC <= TOL THEN 640
570 REM after failure , revise fe/4 for next round
580 FE4 = FE4 - 1
590 TRIAL = TRIAL + 1
600 IF TRIAL <= ALLOW THEN 500
610 TRIAL = TRIAL - 1
620 PRINT "can't find the factors of n after"; TRIAL;" trials"
630 GOTO 970
640 REM for perfect square, complete calc of x, y
650 W = A - FE4 * 2
660 X = W - ROOT
670 Y = W + ROOT
680 REM calculate factoring error
690 ER = INT(X) * INT(Y) - N
700 PRINT "error = "; ER;
710 PRINT ", when second hyperbola has fe = "; FE4 * 4
720 PRINT "factors "; X; Y; " found within"; TRIAL; " trials"
730 IF ABS(ER) > TOL THEN 570
740 REM a second distinct solution is unlikely
750 REM now calculate d for e
760 REM the rest of this program is written by Lloyd Miller
770 REM it is based on the code in the genkeys function of PKSCrypt
780 DIM X(20), B(20), D(20)
790 X(0) = (X - 1#) * (Y - 1#)
800 X(1) = VAL(MID$(E$, 5))
810 B(0) = 0
820 B(1) = 1
830 I = 2
840 REM loop to find e from d and factors of n
850 D(I) = INT(X(I - 2) / X(I - 1))
860 X(I) = X(I - 2) - D(I) * X(I - 1)
870 B(I) = B(I - 2) + D(I) * B(I - 1)
880 IF X(I) <= 1 THEN 910
890 I = I + 1
900 GOTO 840
910 REM found
920 PRINT"the other key for this pair is ";
930 IF I <> INT(I / 2) * 2 THEN 960
940 PRINT X(0) - B(I)
950 GOTO 970
960 PRINT B(I)
970 END
er key for this pair is ";
930 IF I <> INT(I / 2) * 2 THEN