Final Project
Secure RSA Credit Card Transaction System.
Tony Cuadra, Ilyas Elkin
Spring 2000


 
Table Of Contents
Introduction

High Level Design

Program/Hardware Description

Results of the Design

What We Would Do Different Next Time

Appendix A - Listing

Appendix B - Schematics

Appendix C - Encryption

Introduction
In today's world of e-commerce and widespread credit card use, credit card storefront terminals have become common to almost all the stores, and thus big business. They are what allows us to use our credit cards in almost any store in the country. RSA public key encryption has become an industry standard because to crack it, the thief has to factor a number with unknown factorization, and that number can be chosen large enough so that time to factor it would be overwhelmingly large even on the fastest computers. For the final project, we designed a credit card transaction system with RSA encryption that takes credit card input from the terminal and sends it to the server controller, which buffers it, and outputs it to the server PC monitor when necessary or requested. While our system is not as secure as industry strength 56 or 128 bit encryption, because we are limited by the math we can do on this server, it does demonstrate all the important properties and functionality of RSA encryption, and can be scaled up if we were to migrate to a more powerful CPU. 

TOC

High Level Design
We used two Atmel AT90S4414 microcontrollers in this project.  One is the storefront terminal, which takes the account number and the transaction amount from the store clerk through the keypad, displaying them on the LCD as they are being typed in.  It then requests a key pair (more about encryption below), from the server using software UART. It waits for the server to respond, then loops through the account and the cash amount data, encrypting and sending it to the server one bit at a time.
The server receives the data, decrypts it, and stores it in it's memory.  When the memory overflows, it dumps the contents to the PC hyperterminal through the UART.  In addition to these features, the server also allows the "bank operator" to perform some simple functions. These include displaying the table or clearing it without waiting for the buffer to fill up, and also allows the operator to change keys for better security, in which case the server will just go down one entry in it's list of stored keys and use a different pair.
Our encryption strength was limited by the fact that to encrypt a number in RSA, it has to be raised to the power of an encoding coefficient (more details below) , and then reduced mod m (encryption modulus). A simple algorithm called Russian Peasant Arithmetic (I am not lying, that's what it's called in the Math 336 book :) makes it possible to perform this function by simply squaring and reducing mod m several times. (more details below)  Still, to guarantee correctness, we need to be able to do division on any number less then the square of the modulus.  Since the stock division routine we used does 16bit divides, we chose m to be 8 bits, so technically this is 8 bit encryption.

TOC

Program/Hardware Design
Pseudocode
Client side:

Start:
Prompt for an account number. (with a #)
Wait
Get account number input followed by a return (A)
Store in memory one digit per byte.
Prompt for transaction amount. (with a $)
Wait.
Get the amount input followed by a return (A)
Store in memory one digit per byte.
Send transaction request to the server using software UART.
Get the public key pair (e,m) from the server.
Encrypt loop (for all the bytes of acct# and cash$)
Encrypt individual bytes by raising to the e power modulo m using Russian peasant arithmetic algorithm (see the encryption appendix) and send the encrypted value to server.
Wait for server to decrypt (delay).
End Encrypt loop.
Start Over

Server Side.
Start:
Wait for transaction request from client or keyboard input from operator
If there is keyboard input from operator (hardware UART) execute the Keyboard Input routine.
If there is a transaction request from client:
Clear Interrupts, so that operator can't interrupt the critical transfer routine, or change keys in the middle of it.
Check if the transaction table is full.
If full, dump the transaction table to the hyperterminal using Display Table routine, and clear the table using Clear Table routine.
Send the public key pair to the client with software UART
Wait for transmission from client.
One by one, receive and decrypt the bits by encrypting them again with the decoding exponent and store the data in the transaction memory.
Set Interrupts
Start Over

Keyboard Input:
Get the keyboard input from hardware UART.
If “D”call Display Table.
If “C”(Clear Table) set the table index to 0.
If“K” call Change Keys.
return.

Display Table (tblflush):
Print Header to the UART
Loop through all the transactions until the index pointer and print them
return.

Change Keys:
Move the key index to the next one in key table (or go back to 0 if already at the end)
return.

Hardware Design

We don't really have much hardware here, aside from the two Atmel AT90S4414 controllers , Keypad and Hitachi LCD.  The two controllers have connected grounds, and pins D6 and D7 for Duplex Software UART.  The server controller has Pins D0, D1 connected to the hardware RS-232 port.

TOC

Results of the Design
Our credit card transaction system works. We can successfully enter the account number, encrypt send it to the server controller, decrypt, and store it in the "database". We can also view the table, change keys, and clear the table.  On table overflow, the server dumps the table to the UART and clears it as proposed.  So the functionality we set out to implement is there.  The encryption in only 8 bits strong, because we need to be able to divide the square of any number less then the modulus, so the number itself has to be 8 bits if we are to use the standard 16/16 divide and 8x8 multiply from the Atmel website (we need the remainder). However, our encrypt routine does demonstrate all the concepts of public key encryption, which is what we were aiming for, even if it's not industry strength.

Sample Hyperterminal capture
Receiving Transaction:    757265     $0075.27

(c) clear table, (d) display table, (k) change key >

Receiving Transaction:    957276     $7557.27

(c) clear table, (d) display table, (k) change key >

Receiving Transaction:    727646     $0772.72

(c) clear table, (d) display table, (k) change key > d

Account    Amount
537757     $5768.31
757265     $0075.27
957276     $7557.27
727646     $0772.72

(c) clear table, (d) display table, (k) change key > k

RSA key changed

(c) clear table, (d) display table, (k) change key >

Receiving Transaction:    054542     $0005.75

(c) clear table, (d) display table, (k) change key > c

Data table cleared

(c) clear table, (d) display table, (k) change key > d

Account    Amount

(c) clear table, (d) display table, (k) change key >

TOC

What Would We Do Different Next Time
TOC
Appendix A - Listing
TOC
Appendix B - Schematics

TOC

Appendix C - Encryption
Much of the encryption math comes straight out of the Math 336 book.
Some definitions and important properties of numbers that apply to RSA encryption:
Given a modulus m,  a  is a unit of m iff 0<a<m and GCD(a,m)=1.  The number of units  m has is F(m) (actually it's Phi(m), but that's not important here)
If m is a prime, then F(m) = m-1.  Also for any unit a of m, a^(F(m))=1 (mod m).  Consequently, a^(k*F(m)+1)=a (mod m), for any k.  This is the key behind RSA encryption.  If you choose integers e and d, so that e*d =1 (mod (F(m)), then a^(e*d)=a(mod m).  So to encrypt a number, RSA raises it to the e power, and to decrypt, it raises it again to the d  power mod m.  The Russian peasant arithmetic algorithm raises to large powers by squaring the result and reducing the exponent by half, and multiplying the result by the source when exponent is odd, everytime reducing mod m.  because the number is reduced every iteration, there is no need to store a^d number anywhere and then reducing it mod m.  instead, the biggest number stored is a^2, and it is reduced mod m. I wrote this algorithm in C, and then translated it to assembly manually.  Here is the listing of the C code. Notice how the computational load is reduced by using this algorithm.
include <stdio.h>
int main(int argc, char *argv[])
{
int result = 1;
int s=atoi(argv[1]); //the number being encrypted
int m=atoi(argv[2]); //the base
int e=atoi(argv[3]); //the encoding key
while(e>0)
{
if((e%2)==1){
result=(result*s)%m;
e=e-1;
}
s=(s*s)%m;
e=e/2;
}
printf("%d ",result);
}
TOC