How to make a simple public-key cryptographic algorithm? [closed]

Question

I want to make a simple public-key(asymmetric) encryption. It doesn't have the be secure, I just want to understand the concepts behind them. For instance, I know simple symmetric ciphers can be made with an XOR. I saw in a thread on stackexchange that you need to use trapdoor functions, but I can't find much about them. I want to say, take a group of bytes, and be able to split them someway to get a public/private key. I get the ideas of a shared secret. Say, I generate the random number of 256(not random at all :P), and I split it into 200 and 56. If I do an XOR with 200, I can only decrypt with 200. I want to be able to split numbers random and such to be able to do it asymmetrically.

Answer 1

OK, just a simple demo-idea, based on adding/modulo operation.

1. Lets say we have a modulo value, for our example 256. This is a public-known, common value.

2. Let's say you generate a random secret private key in the interval [1-255], for example, pri=133. Keep secret key in the pocket.

3. Generate a public key, pub = 256 - pri = 123. This public key (123) you can share to the world. Imagine, 3rd party does not know, how to compute the private key from a public. So, they know only public key (123).

4. Someone from the public wants to send you an encrypted ASCII-byte. He gets his byte, and adds to it the public key by modulo 256 operation:

   encrypted = (input_value + pub) % modulto;
   

For example, I want to send you the letter "X", ASCII code = 88 in encrypted form. So, I compute:

(88 + 123) % 256 = 211;

5. I am sending you the value 211 - encrypted byte.

6. You decrypt it by the same scheme with your private key:

   decrypted = (input_value + pri) % 256 = (211 + 133) % 256 = 88;
   

Of course, using the simple generation pair in this example is weak, because of the well-known algorithm for generating the private key from the public, and anybody can easily recover the private using the modulo and public. But, in real cryptography, this algorithm is not known. But, theoretically, it can be discovered in future.

Answer 2

This is an area of pure mathematics, there's a book called "the mathematics of cyphers" it's quite short but a good introduction. I do suggest you stay away from implementing your own though, especially in Java (you want a compiler that targets a real machine for the kind of maths involved, and optimises accordingly). You should ask about this on the math or computer-science stack-exchanges.

I did get a downvote, so I want to clarify. I'm not being heartless but cyphers are firmly in the domain of mathematics, not programming (even if it is discreet maths, or the mathsy side of comp-sci) it requires a good understanding of algebraic structures, some statistics, it's certainly a fascinating area and I encourage you to read. I do mean the above though, don't use anything you make, the people who "invent" these cyphers have forgotten more than you or I know, implement exactly what they say at most. In Java you ought to expect a really poor throughput btw. Optimisations involving register pressure and allocation pay huge dividends in cypher throughput. Java is stack-based for starters.

---

Addendum (circa 6 years on)

Java has improved in some areas now (I have a compiler fetish, it's proper weird) however looking back I was right but for the sort-of wrong reasons, Java is much easier to attack through timing, I've seen some great use of relying on tracing compiling techniques to work out what version of software is being used for example. It's also really hard to deal with Spectre which isn't going away any time soon (I like caches.... I feel dirty saying that now)

HOWEVER: above all, don't do this yourself! Toy with it AT MOST - it's very much in the domain of mathematics, and I must say it's probably better done on paper, unless you like admiring a terminal with digits spewn all over it.

Answer 3

http://en.wikipedia.org/wiki/RSA_(algorithm)

Is the standard one on which the (whole) internet is based