Math 511, Breaking Codes with UBASIC

Breaking Codes with UBASIC

UBASIC is a public domain (i.e. free) implementation of the BASIC computer language created by Yuji Kida. It is special because it contains support for integer arithmetic with very long integers (2500 digits) and because it has built-in number theory functions. We will see how to use the features of UBASIC to break RSA public key encryption with 30-40 digit keys (real implementations use 150 digit keys or larger). After this, we will study the algorithms used by the UBASIC program "mpqsx."

Example: We have intercepted the message 73632631261261245 which was encrypted using the public key f(x) = x⁹⁷ (mod 909425361410293587232568645362360387). What was the original message?

We solve this problem using the same techniques as in the last assignment. We start by factoring 909425361410293587232568645362360387. This is a little too big to do by hand, so we use our computer. Start UBASIC (it is available on the computers in the Math-Physics Computer Classroom Laboratory). The transcript of asking the computer to break the code follows. Items in bold are what you type. The rest is the computer's response

load "mpqsx
OK
run
Prime Factorization by MPQS

Input an integer =? 909425361410293587232568645362360387

ADLEMAN Test for 909425361410293587232568645362360387
Power Check  7  6  5  4  3  2
MPQS Method  for 909425361410293587232568645362360387
with  Multiplier= 3 Size= 464
 465
ADLEMAN Test for 113680897410347
ADLEMAN Test for 7999808077935876437321

 909425361410293587232568645362360387 =
 113680897410347 * 7999808077935876437321

Input an integer =? 0
OK

So we have found the factorization we were looking for,
909425361410293587232568645362360387 =
113680897410347 * 7999808077935876437321

This is the longest part of the problem, but it takes less than 5 seconds on my home computer.

Now we use this factorization to find the private key. First we need to find j(n) = (p - 1)(q - 1), which we do as follows.

p=113680897410347
OK
q=7999808077935876437321
OK
phin=(p-1)*(q-1)
OK
print phin
 909425361410285587424377028588512720
OK

Next we find the decryption key d which is the inverse of 97 (mod 909425361410285587424377028588512720). We calculate this as follows

d=modinv(97,phin)
OK
print d
 290641094883699517630471009136534993
OK

Finally we use the decryption key to decrypt the message 73632631261261245 as follows.

m=modpow(73632631261261245,d,p*q)
OK
print m
 184615348709439918052682148044876036
OK

So the original message is 184615348709439918052682148044876036 and we have broken the code.

Of course, the real work in breaking the code is hidden in the program "mpqsx." That stands for Multiple Polynomial Quadratic Sieve (the x indicates that it is written in assembler). This technique of factoring is based on the tricks we encountered last time of looking for repetitions of squares (mod n). Of course it doesn't just look randomly, it has a very specific pattern using some neat tricks to speed things up. We will look at the details of how this algorithm works next time.

One final useful note: To end a UBASIC session, use the command system.