20

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.

user2507230
  • 562
  • 1
  • 3
  • 12
  • 2
    I just want to know how it works, I don't have any uses for encryptions. All of the stuff online explain the outer-shell, but not the generation, etc, of public-key systems. – user2507230 Sep 26 '13 at 00:38
  • 3
    This question appears to be off-topic because it is about crypto theory. – President James K. Polk Sep 26 '13 at 00:39
  • 1
    You need to do some reading about crypto. Get a good book. You can't possibly expect to learn the fundamentals of PK crypto on a site dedicated to specific programming problems. – Jonathon Reinhart Sep 26 '13 at 00:41
  • Seems you could *almost* just as easily say, "You need to do some reading about [LINQ/SQL cursors/code injection/JavaScript prototyping...]" ;^) I'd probably suggest *suggesting* [a good book](http://stackoverflow.com/a/19017448/1028230). Though I understand the OT close, having a basic understanding of crypto probably is germane to programming with apps that use it. [`if your question generally covers… a software algorithm… then you’re in the right place to ask your question!`](http://stackoverflow.com/help/on-topic) – ruffin Mar 05 '15 at 20:44

3 Answers3

30

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;

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

  2. 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.

fedorqui
  • 275,237
  • 103
  • 548
  • 598
olegarch
  • 3,670
  • 1
  • 20
  • 19
  • 1
    I must add: "The best cyphers are known by all" there's a lot of empirical evidence for this (although some forms change their name to 'obscuration') – Alec Teal Sep 26 '13 at 00:59
  • The modulto, is it the shared secret, or just the size of the byte it's in reference to? decrypted = (input_value + pri) % 256 = (221 + 123) % 256 = 88; That % 256, if it was the shared secret, then a simple 256 - 123 would result in the private key? – user2507230 Sep 26 '13 at 01:13
  • I figured it out completely! Thanks man! – user2507230 Sep 26 '13 at 01:33
  • 2
    modulto is shared information. I selected 256, because of adding in the uint8_t automatically doing by modulto 256. So, in the simple implementation, do not needed use this operation. But you can use any another modulto which is more than max_you_byte_value, for example, 150. If pri = 50, then pub = 150-50 = 100. There will work same math: enc = (88 + 100) % 150 = 38; dec = (38 + 50) % 150 = 88. – olegarch Sep 26 '13 at 01:59
  • This answer is WRONG. If the modulo is public information, then the private key is also public information, because you can just subtract the public key from the modulo to get it (as @user2507230 pointed out above). – Sod Almighty May 19 '23 at 15:45
4

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.

Alec Teal
  • 5,770
  • 3
  • 23
  • 50
  • The downvote was thoroughly undeserved so I upvoted – James Robinson Sep 26 '13 at 00:49
  • Java is just-in-time compiled, and certain methods are even implemented as intrinsics inside the JVM. Java is not as slow as you think. – ntoskrnl Sep 26 '13 at 16:39
  • @ntoskrnl there is no obligation for an implementation to have any sort of JIT, even then the JIT must be fast so it does only the most beneficial optimisations on a small bit of code, consider an actual compiler though, with all the compile time in the world, and link time optimisation and the keyword const, you've really got something. GCC for example puts a lot of work into reducing the penalty of abstraction. Java may be faster than just a VM would be, but it is by no means fast. – Alec Teal Sep 27 '13 at 01:51
  • A JIT is not required, but there is only one widely used VM, HotSpot, and it has had a JIT since version 1.2, released in 1998. Given adequate runtime, modern versions of HotSpot eventually compile all parts of the program that would benefit from compilation, not just small bits. A JIT also has much more runtime information about the code than a static compiler like GCC, so unnecessary branches, redundant bounds checks, null checks and even synchronization can be elided dynamically. While Java does lack performance is some areas (such as floating point), it is about has fast as C++ in general. – ntoskrnl Sep 27 '13 at 08:54
  • @ntoskrnl few words, profile guided optimisation. You also can't say "C++ in general" because that can mean SO MANY things. We should avoid the debate really, but it is common knowledge that C(++), Fortran, Go.... so forth, even the vtables are different. There's also memory management and stuff. C++ is not better at floats, it's just that compilers allocate actual machine registers and such. I know a lot about the insides of GCC (and it's Java compiler), fascinating stuff :) – Alec Teal Sep 27 '13 at 15:16
  • GCJ has nothing to do with the HotSpot JIT though, they are completely different beasts. Saying "you shouldn't do cryptography in Java because it's so slow" is misleading because it's not slow in the same sense as, say, PHP is. – ntoskrnl Sep 28 '13 at 10:54
  • @ntoskrnl GCJ with LTO is as good as you're going to get, I think you need to accept that if you want a fast language, you're going to have to learn one, you're being all like "Java is quick", but it cannot be as fast, GCJ is as good as you're going to get, because it's GCC, the backend stuff (-O3, -lto) all work, profile guided optimisation, I used that to tell you your best bet for high-speed Java. Anyway please don't reply to this, I have other things to do, research the issue yourself, please don't reply to this comment. – Alec Teal Sep 28 '13 at 14:36
  • It doesn't take much research to find out how outdated and unmaintained GCJ is; therefore I don't think it's a fair comparison. Because debates like this never go anywhere, I think [this](http://xkcd.com/386/) is appropriate here. – ntoskrnl Sep 28 '13 at 19:00
  • @ntoskrnl The GCC front end supports Java 6, the backend is totally separate, I didn't read beyond that. Thanks for sharing. – Alec Teal Sep 28 '13 at 22:15
3

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

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

James Robinson
  • 1,222
  • 1
  • 15
  • 43
  • 1
    Given that it was invented at GCHQ and the UK government wouldn't even allow its inventors to claim credit when R, S and A filed their patent I think we can be sure its pretty secure. Now your random prime number generator could be full of holes for sure. – James Robinson Sep 26 '13 at 00:41
  • That tells me about how it generates the keys, kinda, but how does it encrypt/decrypt with the keys? – user2507230 Sep 26 '13 at 00:43
  • 2
    Did you read the article? i.e. the paragraphs marked encryption and decryption right at the top – James Robinson Sep 26 '13 at 00:44
  • I figured it out, thanks. :) – user2507230 Sep 26 '13 at 01:11