The Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math

Topic: Communications security
Replies: 0  

Advanced Search

Back to Topic List Back to Topic List  
an581062@anon.penet.fi

Posts: 1
Registered: 12/12/04
Communications security
Posted: Jun 17, 1996 11:54 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply



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.

Bob

**************************************************************************

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:

((FAC1 + FAC2) / 2)^2 - ((FAC1 - FAC2) / 2)^2 [Eq. 1]

Since FAC1 and FAC2 are odd, (FAC1 + FAC2) and (FAC1-FAC2) 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 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.



| 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 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.

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








Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2017. All Rights Reserved.