Saurav R Tuladhar

My own musings

RSA : Public Key Cryptography Algorithm ( Project on Abstract Algebra )

Abstract Algebra was one of the mathematics course I took for the Fall semester which has just ended. The complete course has two parts taught over two semesters. I took the first part and it mainly covered some basic Number Theory and largely Group Theory. As a part of the project I had to a class project and my choice was RSA : A Public Key Cryptography Algorithm. The strength of RSA is based on difficulty in factoring large integers, specially those formed as product of two integers.  The algorithm uses Number Theory concepts of modulo exponentiation, the Euler’s function and the decryption is based on Euler’s theorem. My objectives were to study the algorithm itself and do a simple implementation.

In public key cryptography, the key has a public part and a private part. The public part is made known to everybody where as the private part is kept secret by the receiver ( My PGP public key ). Anyone who intends to send a message to the receiver encrypts the plaintext using the public key corresponding to the receiver. Once encrypted using the public key, the ciphertext can only be decrypted using the private key, which is safe with the receiver.

RSA is a public key cryptography algorithm jointly developed by R. Rivest, A. Shamir and L. Adleman and it was described in  a paper in 1978. The name of the algorithm comprises of the first letters of the three authors surnames.  The algorithm was originally patented by M.I.T. but was released to public domain in September 2000. The algorithm has three steps (1) Key generation (2) Encryption (3) Decryption.

Key Generation

The RSA key pair is generated as follows
* Generate a pair of prime numbers $latex p$ and q<em>
* Compute $latex n = pq$$
* Compute the Euler’s function \phi(n) = (p - 1)(q - 1)
* Find an integer $e$ such that 1 < e < \phi(n) and is coprime with \phi(n) i.e. $gcd(e,\phi(n)) = 1$.
* Find another integer d such that de \equiv 1~\text{mod}(\phi(n)). This is determined using extended Euclidean algorithm which gives ed + k\phi(n) = 1 where $k$ is some integer.
The public key consists of the pair (e, n) and the private key consists of the pair (d, n).

Encryption and Decryption

RSA algorithm uses modulo exponentiation operation for both encryption and decryption. The plaintext is first converted to numeric codes before they are encrypted. For instance, the letters in the plaintext are represented as integers x for example  ‘a’ = 00, ‘b’ = 01 \ldots ‘z’ = 25. Once the plaintext is represented by numeric codes the ciphertext is generated as

c = x^e ~ \text{mod(n)}

The receiver decrypts the ciphertext using modulo exponentiation operation with private key pair as
y = c^d ~ (\text{mod n})

The decryption works as follows:

y = x^{de} ~(\text{mod n})

y = x^{(1 + k\phi(n))} ~(\text{mod n})

Now according to the Fermat’s Little theorem,  for any integer x and prime number p (which is not a factor of x), x^{p - 1} \equiv 1 (\text{mod p}) . Also by definition of the Euler’s function \phi(pq) = (p - 1)(q - 1). Thus

x^{(1 + k\phi(n))} \equiv x ~(\text{mod p})

This is true even when x \equiv 0 ~(\text{mod p}). Following similar argument for the prime number q,

x^{(1 + k\phi(n))} \equiv x ~(\text{mod q})

Combining above two equations according to the Chinese Remainder Theorem, we get

x^{(1 + k\phi(n))} \equiv x ~(\text{mod pq}).

Hence y = x^{de} = x ~(\text{mod n})

( A complete explanation is available in the original paper )

As a second part of the project, I implemented a simple version of RSA algorithm in Python . The program can generate an RSA public and private key pair, encrypt a plaintext string and recover original message from the ciphertext. The keys generated are eight digits long.  The plaintext can be a string ( Roman alphabets only for now, no special characters ). The program can be downloaded here.

Written by Saurav

December 26, 2011 at 8:31 PM

Exploring USRP N210 on Ubuntu

We acquired a USRP N210 unit from Ettus Research.  It was planned to explore MIMO and Radar concepts by implementing simple algorithms on the USRP device. However when we got the device after few months of its release and back then the USRP was still plagued with multiple bugs ( including one in the firmware ). It was no easy task to setup working environment on an Ubuntu system. We came across several problems during installation.  I found only one blog detailing the step by step installation ( and workaround ) then http://www.raullen.net/2011/02/20/hello-usrp-n210-how-to-make-usrp-n210-running/.  Even with the help from this blog, I was unable to setup the working environment in my Ubuntu machine and unfortunately I had to abandon the project then.

A year later, I have decided I want to get the USRP up and running so I can do some cool stuff besides some abstract mathematics. I set out to install the device on a new system ( Ubuntu 10.04 LTS ). And it turns out that Ettus has done a good job of providing a much more detailed documentation on setting up the N210. Here I have made a list of topic and related links that a newbie may encounter when starting with the N210 USRP or in general N-series USRP from Ettus.

The safest / easiest way to setup Gnuradio with UHD environment on Ubuntu is to use the build-gnuradio script:

N210 has issues with the pre-installed firmware and the FPGA code and hence it needs to be updated before the PC can talk with it. The firmware and FPGA images can be downloaded from here 

Front panel LEDs

The LEDs on the front panel can be useful in debugging hardware and software issues. The LEDs reveal the following about the state of the device:

  • LED A: transmitting
  • LED B: mimo cable link
  • LED C: receiving
  • LED D: firmware loaded
  • LED E: reference lock
  • LED F: CPLD loaded

Written by Saurav

December 20, 2011 at 11:49 PM

RMTool for Polynomial Method : The Bottleneck?

I have been reading The Polynomial Method for Random Matrices by N. Raj. Rao and A. Eldeman as a part of literature review for my PhD research. In this paper, the authors present a method to determine the limiting eigen distribution of  a particular subset of random matrices called algebraic random matrices.  In the proposed method, the Stieltjes transform of the limiting eigen distribution is encoded as a root of a bivariate polynomial. A defined set of transformations ( deterministic and stochastic )   on the matrix is mapped to an operation on the bivariate polynomial. The limiting eigen distribution of the resulting matrix can be determined from the new bivariate polynomial.

This method heavily relies on the symbolic computation methodology.  In parallel with the development of the mathematical framework for the polynomial method, the authors have developed a Matlab toolbox called the RMTool which leverages the symbolic computation capability of Matlab. However the RMTool uses the Maple Symbolic Toolbox for Matlab which Mathworks no longer supports (Above version 2009a). The original RMTool might even have been written in Maple itself and later forked to a Matlab toolbox. This has made RMTool extremely platform dependent tool preventing it from being used by other researchers. The method was proposed sometime in 2005 but I can hardly find an alternative reference on this topic or its application. It seems  me that the rigidity of the RMTool may be limiting its potential as a powerful tool in random matrix analysis and application to engineering problems.

I have been looking at possibilities of porting the RMTool to the new Matlab Symbolic Toolbox which is based on MUPad. I am also planning on developing a new package ( from scratch :o) on a more robust and compatible platform ( Python with Sage ). But these ideas are still in early phase and need a thorough understanding of the polynomial. method.

 

 

Written by Saurav

November 9, 2011 at 5:23 PM

Posted in Uncategorized

Nth Prime Number

Python implementation for finding Nth prime number
#!/usr/bin/python

# thousandPrime.py : Finds the 1000th prime number, fork of Problem Set 1 MIT 6.00
# Programmed: Saurav R Tuladhar
# Date: Oct 7, 2011

# Declare state variables
counter = 1;   # Counts number of primes
idx = 1;
testNum = 2*idx + 1;   # Odd numbers > 2 as candidates
primeList = [2];
isPrime = True

while counter < 10000:
        for x in primeList:
                if testNum % x == 0:   # Only check for prime numbers < testNum. Based on Fundamental Theorem of Arithmetic.
                        isPrime = False
                        break

        if isPrime == True:
                primeList = primeList + [testNum]
                counter  = counter + 1

# Reset variables
        isPrime = True
        idx = idx + 1
        testNum = 2*idx + 1 

print primeList[-1]

Written by Saurav

October 14, 2011 at 10:57 PM

Posted in Programming, Python

UASP 2011

I am just back from the Underwater Acoustic Signal Processing Workshop 2011 held at W. Alton Jones Campus, University of Rhode Island. It was a three day conference from 12th – 14th October, 2011.

The chairman of the conference was my advisor Dr. John R. Buck. My lab partner David Hague gave a talk on his Compressed Sensing based active SONAR model inspired by bat’s biosonar capability.

Here are my reflections on the conference:

  • The conference began with a reception banquet dinner where G. Clifford Carter was awarded the UASP Award. Apparently it turns out that G. C. Carter invented the Generalized Cross Correlation (GCC) method for time delay estimation. The acronym for this method matches the initials of Carter’s name.
  • Although the conference was on underwater signal processing, there were three plenary sessions on underwater autonomy which mainly dealt with robotics and control systems oriented design problems for underwater deployment of autonomous vehicles. I was a bit disappointed to see very less of signal processing. However where were one session each on Array processing , Noise Modeling and Acoustics Communications which were in the ball park of my interest.
  • The navy seems to have a huge interest in developing unmanned underwater autonomous vehicles and there a lots of companies and academic laboratories working on this area.  I am not particularly interested on the navy’s perspective on this, but as far as I understand the systems development has largely shifted towards being software based design.
  • Large fraction of presentations were focused on military (navy) applications or the signal processing problems they were trying to solve were from military applications point of view. The focus on military applications was a bit too much for my liking.
  • Certainly there are some civilian applications of the results from these research.
  • There were few presentations on  Synthetic Aperture SONAR (SAS) and I came to an understanding that synthetic aperture is analogous to taking multiple photographs and stitching them together to form a panorama.
  • There was a presentation by Aurther Baggeror on why MFP failed. My perception was that no body was sure why this particular method failed, but they already knew it had died.
  • Interesting discussion on Coherence, brought up by Henry Cox.
  • It was satisfying to see a large fraction of presentations using real field data for validation of their results. In computer simulations everything works :D.

Written by Saurav

October 14, 2011 at 10:15 PM

Fall 2011 at UMassD

The Fall 2011 semester officially commenced from 7th September. In the beginning of the summer I had already registered for a course on Discrete Mathematics ( MTH 550) and also planned to audit the CIS course on Algorithms and Data Structures.. I am also registered for Abstract Algebra (MTH 441) as suggested by my advisor. In addition to all that I am also attending the course on Random Signals and Systems being taught by my advisor.

 

Written by Saurav

September 22, 2011 at 10:24 AM

Posted in Uncategorized

Optimum array paper submitted to JASA [Published]

Last Friday I finally submitted the revised paper to JASA.  During Spring 2011, I and my adviser wrote a journal paper to publish the findings of my MS research on optimum sensor array design. The first manuscript of the paper was submitted to JASA in May 2011. The paper was partially accepted with few comments from the reviewer.

We were able to reply to all the comments but one. I had an intuitive feel to the solution but did not have a rigorous proof to back my intuition.  My adviser always says we should follow our intuition and back it up with a rigorous proof. And over the past week  I eventually came up with a mathematical proof  and we were able to compose a solid response for the revised submission of the paper.

The paper has been published in JASA Vol 130, Issue 5. The permlink to the paper is http://dx.doi.org/10.1121/1.3644914

Written by Saurav

September 3, 2011 at 7:30 PM

Posted in MS Research, Research

Follow

Get every new post delivered to your Inbox.

Join 174 other followers