FPGA based prime number generator for RSA encryption

RSA encryption and decryption algorithm operates with prime numbers. If are familiar with RSA encryption you know that here involves two keys – public and private. In order to generate these we need a two prime numbers p, q to calculate modulus n=pq. Prime numbers are numbers that has no other divisor than 1 and itself and is greater than 1. For instance prime numbers are 2, 3, 5, 7, …

Finding prime number is a first task that FPGA has to do. There are many algorithms that may help finding prime numbers. Cornell university students are using Rabin-Miller Strong Pseudoprime Test probabilistic algorithm that allows to test if number is prime. With large numbers like 1231164598461316549… you cant test all division variants that would take endless time. Anyway theory is way deeper here that we are capable to cover. FPGA is pretty fast to take multiple tests on number to determine prime numbers. And as you guessed these numbers are used to generate RSA keys to encode message. NiosII soft processor is used to help with encryption. They also build a VGA controller to output text for judging the results.


Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *