RSA-Tool 2 Copyright ?2000-2002 by tE! [TMG]
Introduction
Please read this text carefully. This utility has been made for those who
want to use the RSA public key algorithm in their own programs. It offers
creation of strong keypairs and a nice integer factorization feature which
makes use of several differnt factoring methods including the MPQS.
It's possible to factor integers +256 bits in size but please keep in mind
that this can take a *lot* of memory and time ! Thus it's not recommended
to try factoring bigger numbers on slow machines with a few MB of physical
Memory. Don't even think of trying to factor 512 bit numbers for example..
RSA-Tool 2 Features:
- Secure keypair generation
- Key test dialog
- Support of multiple number bases
- Auto base-conversion on select
- Support of numbers up to 4096 Bits
1. About RSA
RSA is a Public Key Cryptosystem developed in 1977 by Ronald Rivest,
Adi Shamir and Leonard Adleman.
Since 09-20-2000 the U.S. Patent #4,405,829 on this Algorithm EXPIRED!
That means that the Algorithm is Public Domain now and can be used by
everyone for free, even in commercial software.
2. Parameters
P = 1st large prime number
Q = 2nd large prime number (sizes of P and Q should not differ too much!)
E = Public Exponent (a random number which must fulfil:
GCD(E, (P-1)*(Q-1))==1)
N = Public Modulus, the product of P and Q: N=P*Q
D = Private Exponent: D=E^(-1) mod ((P-1)*(Q-1))
Parameters N and E are public whereas D is -private- and must NEVER be
published! P and Q are not longer needed after keygeneration and should be
destroyed.
To obtain D from the public key (N, E) one needs to try splitting N in its
both prime factors P and Q. For a large Modulus N (512 bit and more) with
carefully chosen primefactors P and Q this is a very difficult problem.
All the security of the RSA encryption scheme relies on that integer
factorization problem (tough there's no mathematical proof for it).
To find out more read here:
http://www.rsasecurity.com/rsalabs/challenges/factoring/rsa155.html
3. Encryption
To encrypt a messageblock (M) (which must be < N), compute:
Ciphertext = C = M^E mod N.
Note: If the entire message (M) is > N it must be split into smaller
blocks with size < N
4. Decryption
To decrypt a given Ciphertext (C) to retrieve the Plaintext (M) as result,
compute: M=C^D mod N.
The ' ^ ' sign in the above equations means 'power of', not XOR !
Note that the RSA scheme does also work the other way round:
C=M^D mod N and M=C^E mod N. It's on you how you implement it. Just ALWAYS
make SURE that you -NEVER- publish the private exponent D, P and/or Q !
5. How to ...?
...Generate a RSA keypair ?
1) Press the 'Start' Button to collect some (pseudo) random data by moving
around your mousepointer.
This must be done only one time, because the collected data will be
saved in a file in your RSA-Tool folder.
2) Select the number base you want to use for your keys. Base 10, 16, 60
and 64 are available.
3) Select the size of of the key (=size of N) you want to create. Max.
keysize is 4096 bit.
4) Choose your public exponent (E) and type it in the corresponding
Editbox as DECIMAL number.
Most common values (calculation-speed reasons) used for E are:
3, 17, 257 and 65537 (decimal)
5) Press the Generate button and wait until keygeneration has been
finished.
Note that generation of very large keys can take some time, depending
on the power of your CPU.
Important: You can press Generate as often as you like. The internal
random number generation system, which is used in a part of the key
generation process, will be re-initialized during runtime.
This is done on purpose, as it makes it much harder to abuse this tool
for certain things...Note that this also makes it almost *impossible*
to create the same keypair twice or more.
It can happen that your Modulus will become e.g. 159 Bits only, even
when you selected 160 Bits as keysize. The reason is the little size
difference between P and Q. If you are not satisfied, simply press the
Generate button again until the desired keylength meets your needs :-)
...Factor a Number ?
1) Select the correct number base for the number you want to factor.
2) Type in or Paste the number in the Editbox for the Modulus (N). This
enables the 'Factor' button.
3) Press the Factor N button. Note that factoring numbers > 240 Bits can
take a LOT of time and memory !
Even smaller ones can take several hours. If you dont believe me try to
factor a 240 Bit N generated by this tool...
If the multiple polynomial quadratic sieve (MPQS) Algorithm is used to
factor your number, a huge amount of memory is needed.
Reason for this is the design of the algorithm, not a bad coding style.
Examples: Memory usage for factoring a given N (using the MPQS
Algorithm) with size...
256 Bits : ~89 MB, 280 Bits : ~140 MB, 296 Bits : ~185 MB and so
on.
...Calculate the private exponent D from prime factors P and Q ?
1) Select correct number base for parameters P and Q
2) Type in or paste P and Q in the corresponding Text fields.
3) Press the 'Calc. D' button.
...Obtain the -exact- bitsize of a number ?
1) Select the correct number base for the value you want to check.
2) Type in or Paste the number in the Textbox for the Modulus (N).
3) Press the small 'Bits' button. This will show you the -exact- amount of
used bits in the number.
6. Notes
- The Primenumbers used for keygeneration are strong primes and calculated
very carfully.
If you don't trust this tool, don't use it or even better, reverse
engineer the keygeneration and tell me about your worries ;-)
- The bignumber library used in this program is MIRACL 4.45 (c) by Shamus
Software Ltd.
It can be downloaded incl. Sources in C/CPP and manuals at:
http://indigo.ie/~mscott/
The MIRACL library is -not- free to use in commercial programs. Even
worse, the license fees are pretty high. Alterantively you can, of course,
use any other bignumber library - like Freelip for example.
- Used Base60 conversion table (supported by MIRACL):
0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwx
- Used Base64 conversion table:
ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/
Important: Base64 number format is not supported by MIRACL. I used own
routines. Conversion goes from MSB to LSB of the hex representation of
each number. This may be incompatible with conversion routines of your
favourite lib.Sourcecode in C for the base64 conversion comes bundled with
this Tool.
7. Credits and Greetings
This tool has been coded in C by tE! Compiled with MSVC 5.
Greetings fly over to:
Ousir - Quantico - Ivanopulo - GriYo - Daemon - MackT - Recca - Analyst
Dimedrol - Snacker - SAC - VAG - +SplAj - Snaker - Seifer - Sab - NoodleSpa
f0dder - The Owl - Lorian - Defiler - Ultraschall - Seir - Risc - MackT
viruz666 - neoman - all my friends in TMG and *YOU*
tE!
