51

I am currently studying IT at college (UK college aka not University) and the coursework is boring me to death. I have been coding for quite a while now mainly in OO languages such as C# and Java but often get bored and give up quickly because the majority of it is boring UI stuff I hate doing, the projects I come up with rarely have much to do with code design and actually creating algorithms. I want to start writing my own algorithms of sorts and start moving away from the user friendliness side and start learning things that interest me, namely cryptography and compression. I want to write my own encryption algorithm, to encrypt the bytes of a file or string. I have a few questions:

  • Where would I start with this, What books/materials are recommended for starting with cryptography?
  • Do I need extensive cryptography knowledge to get started on a basic algorithm?
  • Will C# be OK for putting an encryption algorithm into practice?

Any help would be sincerely appreciated. I want to start writing code so when it comes to applying to uni, I have something to show for all of my bold claims on my application!

closed as too broad by Steffen Ullrich, Neil Smithline, Iszi, D.W., M'vy Nov 27 '15 at 9:17

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 136
    "Do I need extensive cryptography knowledge to get started on a basic algorithm"? YES. Both designing and implementing cryptographic algorithms is extremely difficult, done only by professionals in teams. Play around all you want, learn, enjoy.... but don't even think about using your own crypto algorithm for real-world encryption. – S.L. Barth Nov 22 '15 at 15:24
  • 7
    this question is way too broad to be answered. Designing an encryption-algorithm can be anything from stuff a primary-school pupil could do (caesar-chiffre for eg) to complex mathematical problems that drive grown mathematicans to despair. – Paul Nov 22 '15 at 15:25
  • 8
    when it comes to applying to uni, I have something to show Don't do this. There are (too) many ways to backfire with an encryption algorithm – deviantfan Nov 22 '15 at 15:43
  • 13
    if you're looking for a set of crypto related programming challenges, I'd recommend lookig at cryptopals.com – Rоry McCune Nov 22 '15 at 17:19
  • 34
    @deviantfan I don't see the issue with this - homebrew crypto is definitely a no-no in production, but showing it off as a hobby project should be fine and at the very least demonstrate programming knowledge even if the crypto itself is bad. – André Borie Nov 22 '15 at 17:25
138

Of course you can start small and implement your own algorithms. But do not assume they provide any security beyond obfuscation.

The difficult thing when it comes to cryptography is finding reasons why something actually is secure. You won't be able to decide that within months and if you feel like you are at that point, you are most probably wrong.

It is much easier to find reasons why things are insecure than reasons why they are secure, so if you want to start somewhere, develop your own algorithms until you think they are secure and then try to find out why they are not and find ways to attack them.

Most mistakes are made when implementing algorithms. So if you want to get a well paid job you could learn how to implement that stuff correctly.

I would recommend starting to implement something like AES and than continue to different operation modes like CBC or CCM and find out why randomness is important. Continue with SHA-2 and HMAC and proceed to asymmetric cryptography. Always check what others did and why they did it and have a special look at side channel attacks and how they are performed. If you are at that point you will find your way to go on.

The reference to start with would be the "HAC", which is freely available online: http://cacr.uwaterloo.ca/hac/

[Edit] A suggestion from JRsz which shall not be buried in the comments. A good book for beginners: http://crypto-textbook.com/

  • 78
    +1 for Of course you can start small and implement your own algorithms. But do not assume they provide any security beyond obfuscation. A lot of people keep saying, "don't do it!", but this provides a good opportunity to learn more. This little disclaimer is excellent. – Mark Buffalo Nov 22 '15 at 17:26
  • 10
    I am more than aware anything I make will not be usable in the real world, this is simply to give me something to learn and work towards. – Confuto Nov 22 '15 at 18:39
  • 5
    @Mehrdad I think that it is simply because his/her algorithm has not been around for 35 years and still unbroken. – mbrt Nov 23 '15 at 8:01
  • 6
    @Mehrdad The reason why RSA is secure is that the RSA problem is hard. You are right. It is hard because no one found way to break it. A student should believe their algo is weak because it is a defensive attitude. IMHO that is more reasonable than assuming their algorithm is secure unless someone breaks it, because those who try may be much less than those who tried to break RSA already. – fr00tyl00p Nov 23 '15 at 9:42
  • 4
    @mbrt: No, my point was that RSA's strength relies on factorization not being broken yet, which is a far stronger claim than "X not being broken yet" for any new cipher X, because factorization is much better understood than X. As I said in my comment, there are assumptions involved, but those assumptions can be spelled out and quantified and are much stronger than just "no-one has broken mbrt's cipher #7 yet". – Rich Nov 24 '15 at 15:18
37

Coursera

Here's my 2 cents:

Join the Coursera Cryptography online class:

The class takes six weeks. Each week there are several lecture videos, a graded quiz and an optional programming assignment. (And these assignments involve implementing crypto parts.)

At the end of the six weeks there is a test.

If you want to be challenged, then this is the right way to go. It is a lot of work. I suggest you plan 10+ hours each week. More if you want to do the programming assignment as well.

(Edit: Here's a table of contents for a previous run of this class.)

Clarification: The programming assignments are just there to generate a deeper understanding of the topic. They are explicitly NOT something that you are then meant to release into the wild.
On the contrary: The "Don't you ever implement this yourself!" message is repeated again and again. (And without giving too much away: Whenever "Just implement it yourself!" is on one of the multiple choice tests, then it's wrong.)

  • I forgot about Coursera, thanks! I am subscribed to Lynda.com but they d not have much on crypto. – Confuto Nov 22 '15 at 18:38
  • 6
    +1 on the class. It is quite challenging. Note that the programming assignments are in C. – Scott C Wilson Nov 22 '15 at 18:54
  • 5
    Actually any language will do. Only results are submitted. Not the implementation. On the forums there are implementations in different languages. Examples are in Python2 though. – StackzOfZtuff Nov 22 '15 at 19:08
21

Start by breaking, not building your own. There's a worrisomely large number of stackexchange posts by people who've written their own algorithms. Take a look around and figure out what's wrong with them. (Don't look at the posted answers.) [Good searches include "Is this secure" and "whats wrong with this algorithm".]

Only when you've found issues in other people's work should you move to trying to implement other people's algorithms. (@stackzofztuff's comment about Coursera is not bad--if I recall, Dan Boneh starts out that way, with more structure than poking here.)

  • Take a look around Can you please explain how to find these posts? Do we have to filter questions by tag, websites, etc.? – A.L Nov 26 '15 at 11:00
  • @A.L, I'm thinking searching by multiple tags would be most effective. Something like cryptography+algorithm or encryption+algorithm. You'll have to dig a bit, but at a glance, I do see a few questions. Although they're largely buried beneath smaller things like mixing algorithms or small obfuscations added to existing algorithm. Lots of stuff that doesn't improve security nor weaken it. I don't agree with Adam Shostack that this is effective. – Kat Nov 26 '15 at 17:33
  • I searched for "Is this secure" and think the first 5 questions are good places to start; I've edited my response to be more crisp. – Adam Shostack Nov 27 '15 at 17:44
13

Bruce Schneier's Applied Cryptography is a must read if you want to start studying this field. I am surprised that nobody suggested it before.

And yes, you need to know a lot about crypto even before trying to roll your own algorithms for fun. Don't even think of using them for real-world problems, though -- there's already a lot of bad crypto around.

Concerning programming, avoid proprietary languages like the plague. I'd suggest C, or even C++.

  • 3
    Why do you say "Concerning programming, avoid proprietary languages like the plague"? My experience is that the code can be converted to C/C++ pretty easily (often almost identical, line for line) if you write optimised code in C# (not that many people do, though…). Also, the C# compiler is now open source (released under Apache 2.0). – Toothbrush Nov 23 '15 at 12:55
  • 1
    C# has also always been publicly documented as a standard, through ECMA if I recall correctly (and that is the standard that Microsoft's compiler is expected to adhere to). – a CVn Nov 23 '15 at 13:45
  • 2
    +1 for Bruce Schneier's book. – tcrosley Nov 24 '15 at 8:01
  • @Toothbrush Then why not using directly C which is open, mature, and widespread. – dr01 Nov 24 '15 at 8:22
  • 1
    @dr01 Sure if you're writing a serious encryption algorithm then you should definitely write it in C so it can be formally reviewed. However if you're just knocking up some code to understand what encryption does then why not use whatever language you're most comfortable with? If the only people that will see it are him and his cat, what difference does it make if it is written in AutoLisp! Maybe Applescript will make a come back and become the new Encryption standard... ;) – Michael B Nov 24 '15 at 11:37
10

A good start would be to implement existing algorithms and learn how they work in depth. For example, the one-time pad algorithm is easy to learn and implement, and studying its strengths and weaknesses will get you started. It will also get you comfortable with the kind of bit-twiddling that's important in cryptography. Doing a search for "one-time pad" will get you started.

  • 2
    But note that ontimepad is a "odd" one (algorithm as well as possible usage), it won't help much in understanding AES etc., which is much more used in practice and has many concepts which an be found in other algos too (etc.etc.) – deviantfan Nov 22 '15 at 15:39
  • 2
    the point that would be relevant for OP about encryption-algorithms is usually not the logic that is implemented, but the math behind it. AES is quite a good example for this. In the code all one can see are some simple bit-shifts and low-level mathematical instructions. The algorithm itself is designed in a way to make the encrypted data look purely random, which requires quite some skills to achieve from the designer, to say the least. – Paul Nov 22 '15 at 15:56
  • One time pad is an interesting case though - it's quite a simple algorithm, and in optimal conditions - unbreakable. It's weaknesses stem from scalability and key exchange, which are non trivial for 'real world' applications. But I don't know it really helps understand the other crypto options, which are way more complicated as a result of needing to deal with trust, key exchange etc. – Sobrique Nov 24 '15 at 12:44
6

Just to pile on to the great answers that are here, with something of a different angle.

If you make the assumption that your v1 algorithm is going to be insecure and awful, and your v100 will be only very slightly better, but equally insecure. (as will your v1000)

With that assumption in mind, you can learn a lot by solving the problems that cryptography has needed to solve in order to become the science it is today. i.e. reinventing the wheel.

Personally I find reinventing the wheel an excellent way to learn a complex task. It gives you something to solve. If that is your thing there are fewer things that are more tricky to solve than cryptography.

That way, you can go to University and say, well I've been designing my own cryptography algorithm as a vehicle for learning how to solve difficult problems. At v50 the algorithm sucks, but these are the lessons I've learnt, the solutions I found, and this is how they're solved in the real world.

There's a big difference between saying I've written a 'good' cryptography protocol and saying I've written a protocol that is almost certainly very weak but the purpose wasn't creating a secure protocol. Personally I'd have a large amount of respect for someone who said the latter. (I'd likely nod to the former - and quickly show him the door)

  • This. OP is looking for an interesting challenge - a chance to learn, not to become the inventor of the Next Big Thing. – Floris Nov 24 '15 at 16:06
3

You can implement already existing encryption algorithms, but designing your own encryption algorithm is one of the most complex matters you could deal with. For a general introduction I highly recommend this channel: https://www.youtube.com/channel/UC1usFRN4LCMcfIV7UjHNuQg/videos or the book "Understanding Cryptography" by Christoph Paar and Jan Pelzl (http://crypto-textbook.com/). I assume you are aiming at symmetric algorithms and I would recomment you to start reading a lot of theory about them, what is safe, was is unsafe (historicle) and explicitly how have current state of the art algorithms made their way to what they are (how was AES developed, chosen, etc).

You will encounter many mathematicle problems when you deal with different attacker models, even in the symmetric part. The asymmetric cryptography is manly based on mathematicle problems and there are some very tricky attacks which are very powerful against asymmetric cryptography.

Bottom line is do not develop your own algorithms, unless you have many years of experience and are very familiar with the topic (all parts of it). Implementing a few of them is nevertheless a good idea, but if you are looking for some kind of project why dont you write a program which uses already existing algorithms and decrypts some data for you. You will enough issues to deal with that, because a secure algorithm is not a guarantee at all for secure encryption. Different operation modes will be important on this matter and some other issues as well.

2

You could follow Scott Wilson's suggestion about the One-Time pad, but with real random data. You can e.g. consider the noise from the computer's webcam. Let the webcam take a few pictures of a static scene, convert the images to 32 bit floating point images, normalize the pictures to the same brightness, take the average and then subtract one of the pictures from the average. If you map negative pixels values to 0 and positive pixel values to 1, you almost have perfectly random bits, that are uncorrelated when the pixels are not too close. Applying von Neumann's algorithm to pairs of bits taken from distant pixels:

(0,1) ---> 0

(1,0)---> 1

(0,0) and (1,1) are discarded

will yield perfect random bits with 0 and 1 having exactly 50% probability.

  • 4
    I'm not sure this answers the question – schroeder Nov 23 '15 at 21:58
  • An easy source of randomness from a computer. Thank you! – user82913 Nov 25 '15 at 19:19
2

Go ahead, write an algorithm but at the end give a task to one of your friends/fellows who regularly deal with cryptography; tell them to break your encryption if they can.

You will notice that they will be able to break it in a matter of minutes and you'll be left stunned thinking as to how many loopholes were there that gave the game away to people with extensive cryptography knowledge (to qoute your words)

This is exactly what happened to me when I was learning to program long ago and wanted to challenge some guys who were smart at such stuff and I failed miserably. So much so they could even decipher the message printed on a paper using just their mind and skills.

You certainly can write one and perfect it over the time but by no means it can be secure anytime soon against the people with that knowledge.

That will be a good starting point (or possibly even a stopping point) on your quest to write your own algorithm :)

Not the answer you're looking for? Browse other questions tagged or ask your own question.