Saurav R Tuladhar

My own musings

Archive for the ‘Programming’ Category

Dialup modem (V.34) start-up signalling sequence: Spectral perspective

If you are one of those who jumped onto the internet bandwagon from the days of dial-up connection, then you must be familiar with a sequence of sounds  the modem makes before the connection was established with the ISP. I started my internet surfing days listening to that peculiar sound. Back in those days I had a vague idea that the modem was actually transferring data over the copper pair line that was only being used for voice before that. But I was I didnt’ know what the strange sequence of sound was.

V.34  is the standard protocol recommended by ITU for modems operating on legacy copper pair. The V.34 allows upto 33.8 kbit/s bidirectional data transfer. ( Refer to Wikipedia for more )

Today I came across a recording of the V.34 dialup modem startup signalling audio sequence (here) and I decided to take a look at its spectral content. The figure below shows the temporal and spectrogram plot of ~18s of of signalling sequence. ( The total startup time for V.34 modem is about 10 – 13s)

Spectrogram

Then I looked up the start up signalling sequence for V.34 protocol and found this paper. Briefly the startup signalling involves four phases which can be summarized infollowing steps ( focus on frequency content of signalling signals ):

Phase I ( Network interaction )

  • A 2100Hz  answer tone modulated with 15Hz sine wave is exchanged. ( The 15Hz modulated sine wave is not distinct in the spectrogram, but I will take faith on the specification for V.34 that it is present )

Phase II ( Ranging and probing )

  • This phase involves three steps :  Initial information exchange [INFO0], Probing & Rangin and a second information exchange [INFO2]
  • The information exchange is done at 600bps using DPSK modulated FDM tones at 1200Hz and 2400Hz
  • Probing is used to estimate channel characteristic. The probing signals consists of set of tones 150Hz apart starting from 150Hz to 3750Hz. However, tones at 900, 1200, 1800 and 2400Hz are omitted.

Phase III ( Equalize and training )

  • This phase consists of a series of signals transmitted between the calling and the answering modem. The exchange consists of a sequence of scrambled binary 1s for fine tuning of the equalizer and echo canceller, and a repeating 16-bit scrambled sequence indicating the constellation size that will be used during. These scrambled sequences are transmitted using a four-point constellation.  The scrambled sequence occupies the entire channel bandwidth.

Phase IV (Final duplex training )

  • This phase consists of a sequence of scrambled binary 1s  using either a 4- or 16-point QAM constellation.

I have tired to identify these sequence of events in the spectrogram above ( Larger version ). All of the signalling sequences listed above can be identified in the spectrogram.  There was at least two set of signalling tones that I could not associate with the specification on V.34 protocol.

( Spent couple of hours this afternoon doing this exercise. Coming around more than 10 years after the days of dialup, this was a nice trip down the memory lane and moreover I can see what was going on the scene everytime my modem dialed up to the ISP )

Written by sauravtuladhar

March 29, 2012 at 10:42 PM

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 sauravtuladhar

December 26, 2011 at 8:31 PM

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 sauravtuladhar

October 14, 2011 at 10:57 PM

Posted in Programming, Python

Follow

Get every new post delivered to your Inbox.