yyyRSA

Download

yyyRSA-1.0.2.tar.gz
You need libgmp in order to compile the program. (should be installed on every GOOD GNU/linux distribution)

What's this?

The README file:

This program uses the GPL license. see the file
COPYING for details. a very important passage will be pasted here, too.:

                            NO WARRANTY

  11. BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY
FOR THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE LAW.  EXCEPT WHEN
OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES
PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED
OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.  THE ENTIRE RISK AS
TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH YOU.  SHOULD THE
PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING,
REPAIR OR CORRECTION.

  12. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING
WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR
REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES,
INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING
OUT OF THE USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED
TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY
YOU OR THIRD PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER
PROGRAMS), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE
POSSIBILITY OF SUCH DAMAGES.

 
this means if somebody can crack your secret messages and does
bad things to you, it is YOUR problem!


What is yyyRSA ?
----------------

A simple program to encrypt and decipher messages with
the RSA asymetrical encryption algorithm.

Alice wants to send Bob a message. Eve can monitor the communication
between Alice and Bob. he can read everything they send to each other.

Bob creates a key.
It will consist of two files. the public key and the private key.

Bob gives Alice his public key.
Eve now also has his public key!
Alice encrypts a message with this public key.
Alice sends the message to Bob
Eve now also has the encrypted message!
Bob decrypts the message with the secret key.

Eve can do nothing, because it is not possible to decrypt the message
with the public key !


How to compile ?
----------------

Make sure you have libgmp proberly installed. should
be present on every somehow gnuish system. make sure
you also have the headers installed, not just the library

./configure
make
make install   # you can leave out this step


Now, what do I have to hack into my keyboard to use yyyRSA ?
------------------------------------------------------------

//

  the following documentation refers to the old yyyRSA fileformat.
  there the numbers were stored in ASCII human readable form.
  this had the disadvantage that real long numbers create line
  widths that are too long for many programs. i.e. some mailers
  truncated the lines. in the new yyyRSA fileformat the numbers
  are encoded and not human readable anymore. anyway the files
  are still ASCII.
  the following descriptions implicitly convert the encoded numbers
  into human readable form. you can do this too by using the
  "numberdecode" program included in the distribution.
  example:
DswClJFGG0Z5RdThAXiSXzk5kLcilsfZzXnhPcY4RhC3k6fFhhfRlS6KyVi9+GTDp0z0aT=
UrHMTB47UjapV8Me5c3W+Hl5GhHNySVxAji+a9Cp4iyfdjZ7TV7njAF2BJKQfOAKTu2wpD=
88QnzGCyRrqdKM3n48joFk627Mw+tPk
  this is ONE number. you see this because the top lines all
  end with a '=' character. only the last line hasn't got the '='
  so it is the last line of the number.
  now start "numberdecode" and paste the number with your mouse.
  you will see:
119608406367811651029648033940680735599245919840283579917206556259482
991525866315223682189875329081413339375699513479964853007374331561297
765985133099659039747792288420019423993506709753540760539498358694231
717330914548282466188971861943142974706859546968357061616107817235471
016490314113608027679854909547677
  which is the actual number. but it is a very very long line.
  you can use the "numberencode" program to convert a number into
  the new encoded form.

                                                                      //

bob> yyyRSA
  RSA --make-keys numbits secretfile publicfile
  RSA --encrypt inputfile outputfile publicfile
  RSA --decipher inputfile outputfile secretfile

  .oO (oh now i understand how to use it)

bob> yyyRSA --make-keys 128 delme.sec delme.pub
  i will now generate two random numbers using Linux /dev/random
  entropy source. you can speed up this process by moving
  your mouse and or beating on your keys and or creating
  harddisk activity and or many other things
  see kernel source if you are curious

  *** Creating p
  generating a random number ...... done
  Seeking next prime number . done
  *** Creating q
  generating a random number ...... done
  Seeking next prime number ..... done
  *** Calculating n
  *** Calculating phi(n)
  *** Creating s
  *** Calculating e...
  The public and secret files are now generated.
  If you want to hack the keys, i.e create the secret
  key using the public key, you have to factorize
  a number that consists of two prime numbers
  and has a size of 127 bits
  If you want to see this number, it is the first entry in both
  the secret file and the public file

  .oO (hmmm. 127 bit key is a "bit" unsecure, i should have used
       6000 bit key instead. let's look at the key)

bob> cat delme.pub
  yyyRSA PUBLIC KEY
  122014424615055279531969978322750663391
  131

  .oO (cool. If someone wants to hack the key, he has to factorize
       n = 122014424615055279531969978322750663391
       that's easy. i just hack it into mathematica and get:
       n = p * q
       p = 9723768467215279363
       q = 12548059430501651957
       hehe. now i can calculate the values in delme.sec before
       looking at it!
       the first line in delme.sec is n
       to get the second line (i.e. the secret key)
       i calculate ExtendedGCD[131 (second line delme.pub), (p-1)*(q-1)]
       and get secret key = 48433206717426523164154991008410336395
       hehe. ain't i cool ? hacking my own key ?
       now let's see if i was right)

bob> cat delme.sec
  yyyRSA SECRET KEY
  122014424615055279531969978322750663391
  48433206717426523164154991008410336395

  .oO (cool. should I really use this weak key to communicate with Alice?
       well, it's just a test, so i now give delme.pub to Alice.)

alice> echo "Hello Bob, this is secret"> secret_message

  .oO (what an important message. Bob will be happy about it)

alice> yyyRSA --encrypt secret_message secret_encrypted delme.pub
  now encrypting. Each dot is 7 bytes .. done

  .oO (hmmm what does the output look like ?)

alice> cat secret_encrypted
  26
  155843277235775890615203446806137757077
  72114323135219358660301927813236038108
  187331627553897194264942243594678508320
  94204027149436526126937573202385711458

  .oO (hmmm. secret_message is 26 bytes long. he said each dot was
       7 bytes long. this means 28 bytes in 4 dots. so that's
       why there are four output numbers. I now send this file to Bob)

bob> yyyRSA --decipher secret_encrypted original delme.sec
  now deciphering. Each dot is 7 bytes .. done

  .oO (i can't wait any longer !)

bob> cat original
  Hello Bob, this is secret

  .oO (oh, stupid alice.)


that's it! Easy isn't it. Eve could have created delme.sec, too.
but only because bob used such a weak 128 bit key !
NEVER GIVE YOUR SECRET KEY TO ANYBODY ELSE THAN YOURSELF!


Why this program ?
------------------

I am studying computer science. I had to learn RSA for an exam.
So I implemented it. And because I implemented it, i also had to
release it!  :-)


How secure is yyyRSA ?
----------------------

yyyRSA is designed to be ULTRA secure. speed doesn't matter,
nor does size of the encrypted message.

It is possible to create the secret key, if you have the public key.
However the algorithm to do this takes too much time, see the next
chapter.

I am not an expert in the field of encryption.
But my code is small and easy. Numeric calculations are done using
the GMP library from the GNU project.
The Code is still very new. I hope some security experts tell me
that my code is secure, or tell me why it isn't.

The Algorithm used is RSA. You cannot do anything wrong with it,
BUT it is tricky to create a "secure" key to use with RSA.
and it is also a bit tricky to encode a file into "secure" numbers,
feed it into RSA and back.

My implementation is based on my personal knowledge of RSA.
I read several notes on hacking RSA on the internet.
I modified my program so that those things shouldn't be possible.

The so called RSA timing attack is possible.
most RSA implementations suffer from this kind of attack.
if you are sure that nobody can measure the time it takes
to DECIPHER a message with your secret key, this attack is no
problem to you.

oh and yes :-) it is possible to find out the size of the original
message. just take the first line in the encrypted message. it
is the file size in bytes of the original message.

Another cool feature: It is not possible to prove that
the encrypted message equals to some plaintext, without
having the secret key.
So if Alice sends "Hello"
and Eve thinks(!) alice sent "Hello" and wants to prove this
by encrypting "Hello" and comparing the result with Alices
encrypted message, he will fail, because the two encrypted
files won't match!
this is because yyyRSA is filling half of the possible data
with entropy. oh yes this is a waste, but ain't we paranoid ?

Another topic: how does yyyRSA generate entropy (i.e random numbers) ?
answer: it uses linux /dev/random for key generation
and linux /dev/urandom for encryption entropy generation.
if you are curious, check the kernel source.
yyyRSA does NOT use an own random number generator.

If you are low on memory, yyyRSA may be swapped onto disk.
Eve could steal your computer and analyze your swap partition
to find the keys on your harddisk, even though you did never
store them on hard disk !


How many bits should my key have ?
----------------------------------

Mathematica can hack a 128 bit key in less than 5 minutes on a 400 MHz PC.
it is said that some organisations can hack 512 bit keys.
PGP (Pretty Good Privacy) sais 1024 bit is "military grade"
I say use 6000 bit keys and be on the safe side.
key generation will take very long. let your computer run it with idle-CPU.
encryption and decryption speed suffers with key size.
it is only practical to use small ASCII files with
important things inside. (passwords, account numbers...)

1 MIPS year is a 1,000,000 instruction per second
computer running for one year)
I found the following table on the internet. trust it or not.

KeySize           MIPS-years to hack the key

512               30,000
768               200,000,000
1024              300,000,000,000
2048              300,000,000,000,000,000,000

Are there any patches ???

Oh yes! J-ESTER worked on a patch to run without /dev/[u]random. not using a real entropy source is a severe security problem though. he even ported the stuff to windows! http://jester.htl.de/ (just look for yyyRSA)

(erikyyy at erikyyy dot de, Erik Thiele)



Back to the homepage