Exploring RSA Encryption

An explanation of how and why RSA encryption works, plus examples on how to use it for yourself.
Example Application

Alice publishes the public key numbers e = 79 and n = 3337. Bob wants to send Alice the message Dr Dobbs. In decimal ASCII the message is 6882326879666683. Break this number string into smaller blocks like so

        688 232 687 966 668 3

To encrypt these blocks, apply the formula

        cipher = char^e (mod n)

to each block.

Let us create a Bc program to handle this calculation. Call your favorite text editor with a command such as able rsatest1.bc and type in the following text.

# rsatest1.bc:  RSA experiment 1
# encrypt or decrypt characters
define modexp(a, x, n) { # return a^x mod n
        auto r
        r = 1
        while ( x > 0 ) {
                if ( (x % 2) == 1 ) {
                        r = (r * a) % n
                }
                
                a = ( a * a ) % n
                x /= 2
        }
        return(r)
}
print "enter the base n (=p*q): "; n = read()
print "enter the key (e or d) : "; e = read()
print "\n"
while ( 1 ) {
        print "enter a character code (or -1 to quit): "
        char = read()
        if ( char < 0 )
                { break }
        cipher = modexp(char,e,n)
        print "cipher = ",cipher,"\n"
}
halt

Now Bob can encrypt his message with the command bc rsatest1.bc. The interactive session looks like this:

   
enter the base n (=p*q): 3337
enter the key (e or d) : 79
enter a character code (or -1 to quit): 688
 cipher = 1570
enter a character code (or -1 to quit): 232
 cipher = 2756
enter a character code (or -1 to quit): 687
 cipher = 2091
enter a character code (or -1 to quit): 966
 cipher = 2276
enter a character code (or -1 to quit): 668
 cipher = 2423
enter a character code (or -1 to quit): 3
 cipher = 158
enter a character code (or -1 to quit): -1

The encrypted message is 1570 2756 2091 2276 2423 158.

Bob can copy this number string into an e-mail and send it to Alice. When Alice receives this message, she decrypts it with her secret key, d = 1019, by calling the same program, with the command bc rsatest1.bc. Her interactive session looks like this:

   
enter the base n (=p*q): 3337
enter the key (e or d) : 1019
enter a character code (or -1 to quit): 1570
 cipher = 688
enter a character code (or -1 to quit): 2756
 cipher = 232
enter a character code (or -1 to quit): 2091
 cipher = 687
enter a character code (or -1 to quit): 2276
 cipher = 966
enter a character code (or -1 to quit): 2423
 cipher = 668
enter a character code (or -1 to quit): 158
 cipher = 3
enter a character code (or -1 to quit): -1

The decrypted string is 6882326879666683, which is the decimal ASCII representation of Dr Dobbs. Alice has received Bob's message.

The program should perhaps say char instead of cipher when it is being used to decrypt a message, but from the program's point of view the two operations are identical. The program doesn't need to know whether you are encrypting or decrypting; it does the same thing in either case.

Bigger Is Better

In practice, large values for p and q should be used to create keys of about 100 digits, or even more. The larger the key strings are, the more difficult it is for an eavesdropper to decrypt successfully the message by brute force. For example, a brute force attack could set up the equation

        cipher = char^e (mod n)

with the known values of e, n and cipher. This implicit equation can, in theory, be solved for char by iterating through all possible values of char until one finds a value of char that generates the known value of cipher.

In our example we used small char blocks of three decimal digits each. To make the values of char large, making brute force decryption impractical, use big values for p and q, say 100 digits each. This way, the number n has about 200 digits. Instead of dividing your message into blocks of three digits each, you can then divide your message into blocks of just under 200 digits each. That should keep brute force cryptanalysts busy for a while.

Big Numbers

To experiment with really big numbers, the compressed file crypto.tgz, which can be downloaded from www.seasurf.com/~jdennon, contains an alternative version of the key generator, called rsakeys1.bc. In this generator, the main program has been rearranged to keep things somewhat more orderly when reading input from stdin and writing results to stdout. The revised program uses the same subroutines modexp() and exteuclid(). Here is the revised main program:

print "enter prime p: "; p = read() 
print "enter prime q: "; q = read()
print "\n"
n = p * q
phi = (p-1) * (q-1)
print " n =  p*q   = ", n
print "\n(p-1)*(q-1) = ", phi
#       print "\nGuess a large value for public key e "
#       print "\n then we can work down from there."
#       print "\nenter trial public key e: "; e = read()
#       print "\nenter a random number: "; rn = read()
        e = n / 3
        rn = read()
        if ( e < n ) { e += rn + n }
        found_one = 0
        while ( e > 0 ) {
                while ( e > phi ) { e = e / 2 }
                if(found_one == 0) { e = e / 2 }
                
                print "\ntrying e = ",e
                gcd = exteuclid(e,phi)
                d = u1out
                if ( gcd == 1 ) {
                        nextgcd = exteuclid(u1out,phi)
                        # print "nextgcd = ",nextgcd
                        if ( u1out == e ) {
                                # print "\nthat one works  "
                                found_one = 1
                                print "\n\nUse private key d:\n",d
                                print "\n\n Publish e:\n",e,"\n and n:\n",n
                                print "\ncipher = char^e (mod n)"
                                print "  char = cipher^d (mod n)"
                                #print "\nenter any positive value"
                                #print " to continue search for next e "
                                #go = read()
                                #if (go < 0) { break }
                        }
                }
        if (found_one == 1) { break }
        e = e - 2       
        }
        print "\n"
halt

To create an input data file for this program, call your favorite text editor with a command such as able rsadata1 and type in three numbers:

        150386117655676543895037387253432987103
        150373872534329871035038611765567654389
        349801523

The first number is p, the second is q and the last number is the guess for the number e, which starts the search for the keys. If asked whether these first two big numbers are primes, be pleased, like Mark Twain, to answer immediately. Say, "I don't know."

Save the text file and then call the modified version of the key generator program with a command such as bc rsakeys1.bc < rsadata1 > keydata. For the example input file rsadata1, the contents of the example output file keydata should look like this:

enter prime p: enter prime q: 
 n =  p*q   = 226141428872874395374925244146915579441951762249300209\
39739772957241398345067
(p-1)*(q-1) = 226141428872874395374925244146915579438944162347400145\
24809696958222397703576
trying e = 753804762909581317916417480489718598139839207497667364657\ 
9924319080553565403
Use private key d:
11996408748608023536238408391172572664696533934155555472164565632938\
50181603
 Publish e:
75380476290958131791641748048971859813983920749766736465799243190805\
53565403
 and n:
22614142887287439537492524414691557944195176224930020939739772957241\
398345067
cipher = char^e (mod n)  char = cipher^d (mod n)
______________________

Comments

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Article content somewhat useful

Anonymous's picture

I found this article while researching RSA for a homework assignment. I found the article somewhat helpful. As a former programmer, it wasn't, but as a student it was worth a look. The soap opera was as bonus.

a b mod m

Anonymous's picture

Does anybody knows how to calculate a b mod m with large number (e.g. 256 bits) using a optimized algorithm that perform quick bit shifting operation which perform faster than computing a b mod m?

One time I found that article in the internet but I can't find it. Does anybody knows?.

how we can find out reminder

Anonymous's picture

how we can find out reminder of negative no. by rsaencryption.

Is

Kolojed's picture

RsA

dhar's picture

HOW CAN WE GENERATE DIFFERENT PRIME NUMBERS ON EACH EXECUTION SO AS TO GET DIFFERENT KEYS EACH TIME FOR SECURITY.. THEN FOR A BUFFER LIKE,
CHAR *BUF="SOME TEXT HERE"........., HOW TO FETCH EACH CHARACTER AND ENCRYPT FROM THIS BUFFER AND PLACE IT THAT POSITION ONLY.. PLZ HELP ME OUT.....

RSA with non-prime numbers

Anonymous's picture

This explanation is very much helpful in clearly understanding of RSA working .
But there is a question,if we intentionally take 'p' and 'q' as a long composite numbers(of 200 digit) ,then will it violate the basics of RSA algorithm?
or it will reduce the level of security?

with regards

it will fuck up! read some

Anonymous's picture

it will fuck up! read some number teory, about the subject. you will (sometimes) not be abel to generate keys, if you don't use primes, and even if you can generate the keys, the encryption will randomly blow up, so whole the algoritme, dosent work.

Re: Exploring RSA Encryption

Anonymous's picture

Nice article, I

Re: Exploring RSA Encryption

Anonymous's picture

My experience has been there are 2 types of people in contact with computational cryptography: 1) theoretical mathematicians and 2) practicing software developers. Both are required and valuable, but it is overly burdesome to make either become an expert in the nuances of the other's field. In other words, software developers are nearly always unavailable for a dissertation on number theory and mathematicians are nearly always unavailable for complete system architecture. Accordingly, it is appropriate that seperate articles are written for each audience, and this article is a perfect fit for software developers.

Link to Dan Boneh's Twenty Years of Attacks on the RSA Cryptosys

Anonymous's picture

With all the talk about Dan Boneh's paper, I figured it was a good idea to provide a link to it. Here is the reference via Cryptonomicon.Net.

Re: Exploring RSA Encryption

Anonymous's picture

I really like this article. It provided a basic overview to encryption that I was looking for. Obviously this is not the ultimate resource for becoming a guru in cryptology. It is a wonderful place to start.

Re: Exploring RSA Encryption

Anonymous's picture

Thank you for positive feedback

confirming validity of the original

intention.

CAUTION CAUTION CAUTION

To further aggravate reader risk with

more disgusting clarity, this irresponsible

author has now published yet another

dangerous dissertation dressed up as

a basic description of "unbreakable" ;-)

encryption, in the April 2003 issue

of "Nuts&Volts" magazine.

Jdennon@seasurf.com

Re: Exploring RSA Encryption

Anonymous's picture

I agree that this is a dangerous article. Now some people will think they know enough about RSA to use it in their programs. They DON'T.

And what about this: "Of course, any numbers can be used for practice. Primes, especially large primes, make it more difficult for an eavesdropper to decrypt your message."

This is nonsense. In general only primes will work, and all proofs about the RSA cryptosystem are based on the assumption that p and q are prime numbers. I would like to see a proof showing that the RSA cryptosystem works even if p and q are not primes :-)

Re: Exploring RSA Encryption

Anonymous's picture

You are an idiot. Don't trash other people's work if you know nothing about your subject. I can show you at least one proof of the RSA algorithm using non-primes so shut the ***** up.

Re: Exploring RSA Encryption

Anonymous's picture

Show me, don't just talk.

Re: Exploring RSA Encryption

Anonymous's picture

Show you what? Are you saying students
should not be encouraged to experiment?
The article shows students how to experiment.
Are you saying this is a bad idea?
What are you saying? Show you what?
Jack Dennon
jdennon@seasurf.com

Re: Exploring RSA Encryption

Anonymous's picture

Some earlier rather bazaar commentary--contributed by some who may be
in positions able to influence students--labeled my suggested simple method,
for experimenting with the RSA algorithm, as "dangerous." Perhaps the
present comment will help encourage students to go ahead and
experiment. So, thank you.
jdennon@seasurf.com

Re: Exploring RSA Encryption

Anonymous's picture

"Bazaar" also is a little bizarre, but
that's what you get for spelling
by ear.
jdennon@seasurf.com

Re: Exploring RSA Encryption

Anonymous's picture

Not exactly true.

p and q need NOT be prime, they need to be prime one to each other.

For example, 10 and 25 do not work, but 10 and 49 do ...

It remains true however that the original article made a false statement.

In particular you can not just use any binary sequence and use it as a p

or q ...

Re: Exploring RSA Encryption

Anonymous's picture

But the article did not say you can "use" them,

it said you can "practice" with them, as indeed

you can. You can practice with anything you

wish; the whole purpose of which would be

to find out for yourself what works and what

does not.

Re: Exploring RSA Encryption

Anonymous's picture

Yes, that's right. If he had said "any numbers can be

used for practice" and put a period on it, he may have

escaped unscathed; if by "practice" we mean experimenting

to discover what works, but he got a little too chatty and went

on to imply that any numbers work while some just work better

than others. That is indeed false.

Re: Exploring RSA Encryption

Anonymous's picture

Yes. If you read any of the canonical works on RSA, for example the RSA website, you will see that p and q are defined as being prime right at the outset. There are certain composite numbers that will work for this purpose, but there's no way to guarantee that there's no easy backdoor for them. In fact, the large primes used in "real" RSA are pseudo-prime, that is, they *may* be composite but exhibit enough primality to work. In other words, there may be divisors greater than one, but not very many (perhaps one or two).

Thanks

Anonymous's picture

despite the other postings...

I know nothing about security algorthms, but have been curious about how they work.

I, for one, appreciate the article both for what it has, and for what it doesn't.

Re: Exploring RSA Encryption

Anonymous's picture

Actually, this is a horrible article. Okay, you've explained the underlying math in a reasonably clear manner. However, you've given no guidance whatsoever for how to use RSA securely. If people start with this article and use it to implement, they probably won't. For details on the many, many things that can go wrong, see Dan Boneh's paper, "Twenty years of attacks on the RSA cryptosystem".

Then, there's no discussion of other practical issues, such as the fact that RSA is not something you'd ever want to use for general-purpose encryption. Not only are there massive efficiency issues, but also RSA is highly prone to dictionary-style attacks.

And then, he doesn't mention any of the more easily accessible RSA implementations, such as the one in OpenSSL.

This article reads like it is written by someone who didn't understand the math 2 weeks ago, learned it and wanted to solidify the knowledge by writing about it. That's all well and good, except you're doing a disservice to the rest of the world.

Re: Exploring RSA Encryption

Anonymous's picture

This article is good. It explains how RSA works, not how to implement it or use it securely for your own stuff. Once you know how it works, it's easier to read up on those.

Re: Exploring RSA Encryption

Anonymous's picture

It's fine for explaining the math, but is horrible at everything else. You can say that it's not intended to be more, but it's still highly irresponsible.

Why? Because you have to assume that people are going to read this article and go, "wow, now I can go add RSA to my system!" without doing a lick of additional research. Such people aren't going to go learn about the importance of the padding scheme, etc.

The math is not the thing that the average developer needs to know about RSA. It's only the "cool" thing.

Re: Exploring RSA Encryption

Anonymous's picture

Highly irresponsible?

So by your reasoning if there were to be an article published on "basic" kernel hacking that would also be irresponsible because now someone is going to go "wow, now I can go hack my kernel!" without doing a lick of additional research.

I think just plain silly.

If you are truly worried about people not having enough knowledge why not share some resources instead of just bitching about it?

Re: Exploring RSA Encryption

Anonymous's picture

No, this is not a "basic" topic. It's an advanced security topic dressed up like a basic topic. If you just follow the article, it will likely be a security disaster, and yet there are no such warnings. That's completely different from basic kernel hacking.

I *did* share resources, recommending the Dan Boneh paper.

In general, people who don't know anything about cryptography should be using high-level protocols instead of relying on articles like this, which will only lead to trouble.

If only people knew that.

Re: Exploring RSA Encryption

Anonymous's picture

Alright now buddy. Why don't you just pop a valium or two and find a different line of work? If you keep on ranting and raving like this it won't be long before you have a nervous breakdown.

on the advisability of getting rid of p and q

Anonymous's picture

Hey, this is a great article about RSA. It's accurate and accessable by the non-specialist. There is, however, one little nit-pic I'd offer. For at least a decade now, most commercial implementations of the RSA algorithm use a CRT (Chinese Remainder Theorem) based algorithm to decrypt RSA encrypted messages. This technique allows one to decrypt a message by using two modular exponentiations with numbers that are half the size of the original key. In order to use this optimization, however, one must keep p and q (not only n) as part of the private key.

There's a good explaination of the technique at: http://people.atips.ca/~walus/Mont/crtexp.html.

Re: on the advisability of getting rid of p and q

Anonymous's picture

Just hold onto the input file you create for the

key generator, then use it as input to the CRT.

BTW, in her 1939 book "Cryptanalysis," Helen F. Gaines

drew a distinction between the terms "decrypt"

and "decipher." Alice "deciphers" Bob's message;

Eve attempts to "decrypt" it.

Such usage nowadays is "historical," for according to

Bruce Schneier's 1994 book "Applied Cryptography,"

in the current lexicon, decipher and decrypt appear

to have become synonyms.

Webinar
One Click, Universal Protection: Implementing Centralized Security Policies on Linux Systems

As Linux continues to play an ever increasing role in corporate data centers and institutions, ensuring the integrity and protection of these systems must be a priority. With 60% of the world's websites and an increasing share of organization's mission-critical workloads running on Linux, failing to stop malware and other advanced threats on Linux can increasingly impact an organization's reputation and bottom line.

Learn More

Sponsored by Bit9

Webinar
Linux Backup and Recovery Webinar

Most companies incorporate backup procedures for critical data, which can be restored quickly if a loss occurs. However, fewer companies are prepared for catastrophic system failures, in which they lose all data, the entire operating system, applications, settings, patches and more, reducing their system(s) to “bare metal.” After all, before data can be restored to a system, there must be a system to restore it to.

In this one hour webinar, learn how to enhance your existing backup strategies for better disaster recovery preparedness using Storix System Backup Administrator (SBAdmin), a highly flexible bare-metal recovery solution for UNIX and Linux systems.

Learn More

Sponsored by Storix