I'm re-posting because I noticed that one line of the code got line-wrapped. Before you cut and paste it to a QBasic program, maximize your screen and set the proportional font for your browser small enough to get rid of all line-wrapping. The program works flawlessly, but only for positive numbers up to 255 digits each, counting the decimal point. Let me know if you want negative number handling, or write it yourself.
There has been a lot of discussion lately about the existence or non- existence of a "back-door" to PGP. I am convinced that there is a mathematical backdoor.
Prime numbers have some unique properties, as do the products of two prime numbers. I feel that there are some strategies which can be explored in cracking RSA other than the brute-force method. I also feel that the lack of true uproar on the part of the establishment, over the supposed existence of this "secure" means of communication, is a strong indicator that PGP is not secure.
The most promising property of the product of two prime numbers is that this product can always be expressed as the difference of the squares of two integers. Let's call the two prime numbers FAC1 and FAC2. Further, let's assume that FAC1 is the larger of the two. The product of the two can be expressed as:
Consider a table with zero and all positive integers, representing ((FAC1 + FAC2) / 2), across the top of the columns, and zero and all positive integers, representing ((FAC1 - FAC2) / 2), down the left end of the rows, and the body of table giving column^2 - row^2 , as below:
Products of prime numbers will appear in the table above twice only: once as per Eq. 1, and once as per Eq. 2. Further, the Eq. 2 solution will always be found in the upper left-to-lower right diagonal immediately above that containing all zeros. Consider the specific case of 55, which is the product of the prime numbers 5 and 11. Inspection of the table will reveal that it is located at column 8, row 3, indicating that 55 can be expressed as 8^2 - 3^2. Also notice that the diagonals leading upward from 55 in the table terminate at 5 and 11 (FAC1 and FAC2).
Now consider the table below, in which the values from the body of the table above have been subtracted from 55 (the product of the primes 5 and 11). This table has many interesting properties which may well lead to "cracking" RSA.
1. The diagonals leading from the tops of columns 1, 5, 11, and 55 are the only ones in which the increment in the value of the diagonal will divide evenly into the the value itself.
2. Column 8 is the only one that is topped by the arithmetic inverse of square, even to infinity.
3. Row 3, if it were continued to the left, would be the only one terminates in a square (64).
And many other properties that, I feel, will eventually allow the examination of a few values and the subsequent determination of the direction in which the 0 at the intersection of the diagonals leading from the factors lies. I've been writing this for days, but keep putting off the mailing, because I always feel that I am very close to an answer.
Also realize that the equation COS(pi * x) * COS(pi * product/x) = 1 has only four solutions: 1, FAC1, FAC2, and the product. If x is plotted along the x-axis, at integer increments, and -COS(pi * product/x) is plotted along the y-axis, and if further, the two factors are within approximately +/- 20% of the square root of the product, then the first positive peak on either side of the square root ARE THE FACTORS. If, unluckily, your PGP factors fit this description, then your's is already "cracked". Hell, I could crack it. Mathematicians note that the resultant graph is not the actual graph of the equation, but is "aliased" by the sampling interval. I am fairly confident that a more mathematically sophisticated sampling interval will also yield the factors. Try plotting th graph for product = 8881 (87*107), at integer values of x, from say, 60 to 120, you'll see what I mean.
Now, you may ask, doesn't the magnitude of the numbers require a "supercomputer"? No, the sheer quantity of mathematical calculations required for a "brute force" approach is what requires a supercomputer. There may be math software available which can handle numbers of this magnitude, I don't know, but I've attached at the end of this posting a QBasic program which I wrote that will take two numbers of up to 255 digits each and give a result of up to 510 digits. It's extremely inefficient, even for a Basic program, because I was performing pair-wise multiplication to facilitate a particular modified brute-force approach which I have since abandoned. Multiplying two 255 digit numbers takes about 27 seconds on my Pentium 75 from the Windows DOS prompt. It could be made MUCH faster. I had intended to write a whole suite of mathematical functions if that particular approach had looked more promising. Since I am now finding potential areas of research for a methodical, mathematical solution, I don't bother with huge numbers anymore, I work more in spreadsheets. When we find a mathematical solution, we'll make the "big number" tools that we need if they're not available.
This issue is larger than just communications security. One of the selling points of the cashless society is that it will be much more secure than a cash based society. Realize, however, that if you get a counterfeit bill, or if you have your wallet lifted, you only lose the cash that you had. If your bank should fail, then shame on you for banking in the first place. However, if someone deletes your number in a cashless system, or untraceably zeros your account, you are permascrewed. I won't even bother going in to the other potential abuses of a number-based system.
On the issue of encrypted communications in general, I will say that I will not grovel or cower before the Government. I do nothing illegal, and I will not sneak. It feels good to finally walk upright again.
PS I'm not a programmer, so if my program looks ugly, it is ugly. I'm not a math major, either. I took calculus by independent study through the University of Arkansas.
'CRUNCHER.BAS 'BOB SHEARER, 1996
RESP$ = "Y" WHILE (RESP$ <> "N" AND RESP$ <> "n")
INPUT "FIRST NUMBER ", FAC1$ INPUT "SECOND NUMBER ", FAC2$ IF FAC2$ = "" THEN FAC2$ = FAC1$
TIME1 = TIMER
FAC1LEN = LEN(FAC1$) FOR DECCHECK = 1 TO LEN(FAC1$) IF RIGHT$(LEFT$(FAC1$, DECCHECK), 1) = "." THEN FAC1LEN = LEN(FAC1$) - 1 NEXT
FAC2LEN = LEN(FAC2$) FOR DECCHECK = 1 TO LEN(FAC2$) IF RIGHT$(LEFT$(FAC2$, DECCHECK), 1) = "." THEN FAC2LEN = LEN(FAC2$) - 1 NEXT
REDIM SHARED FAC1DIG(PAIRS) AS INTEGER FOR FILL = 1 TO PAIRS FAC1DIG(FILL) = 0 NEXT FILLADD = 0 FAC1DEC = 0 IF LEFT$(FAC1$, 1) = "." THEN FAC1DEC = LEN(FAC1$) - 1 FOR FILL = 1 TO FAC1LEN IF LEFT$(RIGHT$(FAC1$, FILL), 1) = "." THEN FAC1DEC = FILL - 1: FILLADD = 1 FAC1DIG(FILL) = VAL(LEFT$(RIGHT$(FAC1$, FILL + FILLADD), 1)) NEXT
REDIM SHARED FAC2DIG(PAIRS) AS INTEGER FOR FILL = 1 TO (PAIRS) FAC2DIG(FILL) = 0 NEXT FILLADD = 0 FAC2DEC = 0 IF LEFT$(FAC2$, 1) = "." THEN FAC2DEC = LEN(FAC2$) - 1 FOR FILL = 1 TO FAC2LEN IF LEFT$(RIGHT$(FAC2$, FILL), 1) = "." THEN FAC2DEC = FILL - 1: FILLADD = 1 FAC2DIG(FILL) = VAL(LEFT$(RIGHT$(FAC2$, FILL + FILLADD), 1)) NEXT
FOR PAIR = 1 TO PAIRS FOR FAC1FILL = PAIR TO 1 STEP -1 MULT = FAC1DIG(PAIR) * FAC2DIG(FAC1FILL) COLUMN = PAIR + FAC1FILL - 1 COLDIGSUM(COLUMN) = COLDIGSUM(COLUMN) + MULT MOD 10 COLCARSUM(COLUMN) = COLCARSUM(COLUMN) + ((MULT - MULT MOD 10) / 10) NEXT FAC1FILL FOR FAC2FILL = PAIR TO 2 STEP -1 MULT = FAC2DIG(PAIR) * FAC1DIG(FAC2FILL - 1) COLUMN = PAIR + FAC2FILL - 2 COLDIGSUM(COLUMN) = COLDIGSUM(COLUMN) + MULT MOD 10 COLCARSUM(COLUMN) = COLCARSUM(COLUMN) + ((MULT - MULT MOD 10) / 10) NEXT FAC2FILL NEXT PAIR
CARTEMP = O FOR ADD = 1 TO COLUMNS COLDIGSUM(ADD) = COLDIGSUM(ADD) + CARTEMP CARTEMP = (COLDIGSUM(ADD) - (COLDIGSUM(ADD) MOD 10)) / 10 COLDIGSUM(ADD) = COLDIGSUM(ADD) MOD 10 CARTEMP = COLCARSUM(ADD) + CARTEMP NEXT COLCARSUM(COLUMNS) = COLCARSUM(COLUMNS) + CARTEMP
PRINT PRINT "THE PRODUCT IS" PRINT
LEADZERO = COLUMNS WHILE ((COLDIGSUM(LEADZERO) = 0) AND (LEADZERO > (FAC1DEC + FAC2DEC))) LEADZERO = LEADZERO - 1 WEND FOR ANSWER = LEADZERO TO 1 STEP -1 OUT$ = STR$(COLDIGSUM(ANSWER)) IF ANSWER = (FAC1DEC + FAC2DEC) THEN PRINT "."; PRINT RIGHT$(OUT$, 1); NEXT