Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Communications security
Posted:
Jun 17, 1996 11:54 PM


I'm reposting because I noticed that one line of the code got linewrapped. 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 linewrapping. 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.
Bob
**************************************************************************
There has been a lot of discussion lately about the existence or non existence of a "backdoor" 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 bruteforce 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:
((FAC1 + FAC2) / 2)^2  ((FAC1  FAC2) / 2)^2 [Eq. 1]
Since FAC1 and FAC2 are odd, (FAC1 + FAC2) and (FAC1FAC2) will both be even. Therefore, ((FAC1 + FAC2) / 2) and ((FAC1  FAC2) / 2) will both be integers.
The product can also be expressed as:
(((Product + 1) / 2)^2  ((Product  1) / 2)^2) [Eq. 2]
as can all odd numbers.
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:
 0 1 2 3 4 5 6 7 8 9 10 11 ... ... ___________________________________________________________ 0 0 1 4 9 16 25 36 49 64 81 100 121 ... ... 1 0 3 8 15 24 35 48 63 80 99 120 ... ... 2 0 5 12 21 32 45 60 77 96 117 ... 3 0 7 16 27 40 55 72 91 112 ... 4 0 9 20 33 48 65 84 105 5 0 11 24 39 56 75 96 6 0 13 28 45 64 85 7 0 15 32 51 72 8 0 17 36 57 9 0 19 40 10 0 21 11 0 . . . . . .
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 lefttolower 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.
 0 1 2 3 4 5 6 7 8 9 10 11 ... ... ____________________________________________________________ 0 55 54 51 46 39 30 19 6 9 26 45 66 ... ... 1 55 52 47 40 31 20 7 8 25 44 65 ... ... 2 55 50 43 34 23 10 5 22 41 62 ... 3 55 48 39 28 15 0 17 36 57 ... 4 55 46 35 22 7 10 29 50 5 55 44 31 16 1 20 41 6 55 42 27 10 9 30 7 55 40 23 4 17 8 55 38 19 2 9 55 36 15 10 55 34 11 55 . . . . . .
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 xaxis, at integer increments, and COS(pi * product/x) is plotted along the yaxis, 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 pairwise multiplication to facilitate a particular modified bruteforce 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 numberbased 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.
Bob
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")
CLS
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
PRINT PRINT "FACTOR 1 LENGTH = "; FAC1LEN; "DIGITS WITHOUT DECIMAL POINT" PRINT "FACTOR 2 LENGTH = "; FAC2LEN; "DIGITS WITHOUT DECIMAL POINT" IF FAC1LEN > FAC2LEN THEN PAIRS = FAC1LEN ELSE PAIRS = FAC2LEN COLUMNS = 2 * PAIRS + 1
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
PRINT PRINT "FACTOR 1 DECIMAL PLACES = "; FAC1DEC PRINT "FACTOR 2 DECIMAL PLACES = "; FAC2DEC REDIM SHARED COLDIGSUM(COLUMNS) AS INTEGER REDIM SHARED COLCARSUM(COLUMNS) AS INTEGER
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
TIME2 = TIMER PRINT PRINT PRINT PRINT "CALCULATION TIME WAS"; TIME2  TIME1; "SECONDS." PRINT INPUT "MULTIPLY ANOTHER PAIR? (Y/N)? ", RESP$ WEND



