Slashdot Mirror
Cryptology Research for High School Student?
John3 asks: "My daughter is enrolled in an Advanced Science Research (ASR) course, at the local high school. The students join the program in 10th grade, choose a research topic, and then locate a mentor to work with them on their topic until high school graduation. My daughter took a cryptology course this past summer, and now she has chosen cryptology for her ASR topic. Most HS students pick mainstream research fields (medicine, genetics), so her science teacher is a bit unsure of where my daughter might locate a cryptology research project appropriate for advanced high school students (especially one that doesn't require security clearance). I'm hoping my fellow Slashdot readers might know of current cryptology/cryptography research projects that offered opportunities for a high school student to participate."
She needs to visit the math department of her local university.
--I gots 99 problems but a new machine ain't one!
AMD! Asus! Whoot! 6 years!
Just give her access to all the texts and digital paper libraries she may need. After a while, she'll naturally acrue enough knowledge to start interacting with profs in the field and have interesting ideas.
The key point is for her to clock in the background knowledge by spending time each day learning more. However, it needs to be self motivated with no outside pressure, else it won't be a fun and trully motivated effort.
Not exactly on topic of finding a mentor, but this request reminded me of my early Computer Science studies when my friends and I took turns coming up with encrypted strings, posted them on a newsgroup we frequented, and made it into a competition as to who could decrypt it first.
We started with simple stuff like letter substitution, ROT13, etcetera. And then moved on to masking and all sorts of fun/complicated algorithms. This was very educational, in the sense of learning about cryptography. We learned interesting concepts, and rapidly developed tools/scripts/methods for attempt to decrypt arbitrary strings.
Much fun.
- shazow
Why not have them replicate some existing work? That's usually a good way for folks to get a feel for what's going on. Since the MD5 collision source code got published recently, why not have them try to replicate that?
2 cents,
Queen B
HDGary secures my bank
It is extremely hard to suggest anything here unfortunately. Most mathematical research in this area requires a very strong background, and students generally just don't have the experience. The best thing you can do is point her at relatively new areas. Along those lines, I suggest quantum computing. Very few people "get" quantum computing right now, and its relatively easy to get started. From the description of the other course I gather she can program in some sort of language. Get her to simulate quantum computations on a regular computer - use a high level programming language. Then you can start investigating quantum algorithms. Start with simple algorithms like searching and sorting, and build up to quantum algorithms like Shor's algorithm for factoring integers. For the research component, have her try to devise a quantum algorithm for some sort of problem. Relatively few people have looked at this, so the field is wide open.
In Soviet America the banks rob you!
Be wary of lock-in mechanisms like in some EU states where H.S performance dictates -generally- one's educational path. But with this aside, America should pursue challenging coursework for H.S age students. Linking market demand with student interest. It is underapprecatied how Indian math education [c.s probably also] is ahead of the U.S in highschools. Too bad there's no standardized certification program for such advanced h.s coursework mediated through the web by a federal authority...
There are plenty of jobs our there that deal with encryption that don't require a security clearence, or much math. Heck, Adobe was using ROT13 for parts of their drm in 2002...
.gov and .edu institutions that have hundreds of man-years of math research to build from.
The point is, lots of companies now use encryption in their products, and there is lots of interesting research to be examined about how products are using encryption (lots of products do it pretty bad, but a few do it really well). Go find a drm product, or vpn product, or any wifi developer and they will be doing something with crypto. Look at the work by the girl who optimized DES (? irrc, might have been aes) as her high school project.
That being said, if you think you've got a new encryption algorithm at that age, you will probably see it as an example problem in your crypto classes later on in life. Leave new algorithm to the
Sera
Slashdot, where armchair scientists get shouted down and armchair theologians get modded up.
http://www.mathismylife.org/ --CMST (center for math science and technology) has/had a really good summer program in classical cryptanalysis funded by the NSA and taught by employees of the NSA. I took it several summers ago -- very interesting. Very diverse age-group in it, but it was a very challenging course and provides a good base for entering the cryptology field -- they started off with basic mono-alphabetic shifts, and worked their way up to matrix-based algorithms and statistical analysis. At the end there's something crazy like a challenge with 23 different cryptograms that must be solved (that no one almost ever does)...something to look into, though this year it looks like they're having trouble finding a venue.
Now then, Dmitri, you know how we've always talked about the possibility of something going wrong with the Bomb...
CPRM might be a bit advanced for high school, but a practical break is an undergraduate homework assignment. (Hint: Assume you have known plaintest for the encrypted media key. How many trial encryptions do you have to do before finding a player key?)
Note that this is a PROTOCOL, not a CIPHER. You can build a flimsy building out of indestructible bricks, and people do it all the time.
In general, the best possible exercise is breaking something, even if it's a bit of a straw man. Implement a discrete log solution (given g, p, and y = g^x mod p, find x) for composite p with known factors less that some convenient limit like 2^32. Or show how to recover a DSA secret key given two different signatures with the same k (and thus r).
If you are serious about finding someone locally who would be able to help mentor, I would try the local university. Depending on what kind of institution is available, you should find at the bare minimum a PHD in computer science who might have some knowledge about the subject who could be a mentor. If your university has a good computer science dept, you might find post graduate students and post doctorate students doing research in this very area with a professor guiding them. Best thing to do would be to talk to the computer science dept. at the local university, and if possible talk to the chair of the dept. explaining what you are trying to do, what kind of time commitments a mentor might have, and how your daughter could get involved. Best case senario, your daughter will be on the fast track to being accepted to a computer science program in the best schools in the world for her college level experience.
I haven't lost my mind!
It is backed up on disk...somewhere...
but the NSA has a website just for kids that has some puzzles, basic crypto problems, and simple ciphers. They call it the page for "Americas Future Codemakers & Codebreakers". They also have crypto-themed cartoon characters like Rosetta Stone and Decipher Dog.
I don't mean to be insulting, but there's no way she could comprehend anything for which she would require security clearances. OK, I suppose it's logically possible, but if she had the mathematics background necessary to it, she wouldn't need your advice for sources of information. Just take her to a university library and look for books in the field from the "Undergraduate Texts in Mathematics" (also called "UTM"s) by the Springer-Verlag publishing house. If she doesn't get that, she's in over her head.
After all, I am strangely colored.
I think I'm more qualified than most to answer this, since I in fact wrote my first published paper when I was in high school, and it was on cryptography. Most of cryptography is just maths, which is actually more accessible to beginners than other subjects since you don't special lab equipment. I'd say the best way to get into it is to think of a cryptographic problem you'd like to solve, and then just work on it. The problem that got me started was how to prove that you're a member of some group without revealing your identity. There are many different solutions, with different tradeoffs -- so even if a problem is supposedly solved there is often scope for new solutions.
For an idea of where cryptography research is going these days, she should read eprint.iacr.org. A lot of those papers are pretty technical and heavy going, but it will at least give some starting points.
The biggest problem I'd see is not finding a feasible problem, but finding a teacher capable of marking it. I know none of my high school teachers could have marked my cryptography research.
Before you can answer that question, you have to figure out what is meant by "research". There's fairly little in the area that professional cryptographers consider to be research that would be accessible to even a very precocious high school student.
However, it's doubtful that the intention of this project is actually to advance the state of humanity's cryptographic knowledge. Realistically, the goals is to find a challenging and educational project for the student, and something that is not obvious to most non-cryptographers.
Given appropriate expectations, I think there are lots of things a fairly sophisticated high school student could do that would be worthwhile, particularly if you want to look beyond cipher design. Some of the areas that might be interesting include:
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
I went to a Magnet high school (http://mbhs.edu/departments/magnet/) (a public school that takes in the top 100 students from the county to teach them an advanced curriculum) and part of the requirements for earning a Magnet diploma was to do a Senior Research Project (SRP) that sounds very much like ASR. To find a mentor (I wanted to do theoretical computer science, I had done some independent research on graph theory in my own time) I emailed a professor at the University of Maryland and worked over my 11th grade summer with him. I came up with a result, not important enough to get published, but it won me this award: http://www.sciserv.org/sts/64sts/Forbes.asp and got me into MIT.
For advanced topics such as cryptography the best bet is the local university. There are also a bunch of government facilities out there that do research. Some of the best places (mostly in the DC area, however) are the NSA (http://www.nsa.gov/careers/students_1.cfm) and NIST (http://csrc.nist.gov/) (NIST can offer housing, btw). There is also a great program for high school juniors at MIT or Caltech (no cost): http://www.cee.org/rsi/index.shtml .
Just to show that high-school cryptography research is possible: http://www.sciserv.org/sts/60sts/Dunn.asp . This guy is the older brother of one of my friends (both who went to the same high school program as I) and I believe he did his research at NIST.
-Michael Forbes
Cryptography in its modern form certainly has areas an exceptional high school student could explore, but I suspect most students would be daunted or bored by most work in it.
However there's lots of exciting forms of information leakage exploits that a high school student with a modicum of math & computer background could explore, especially if they spent a little while studying an introductory machine learning or information theory textbook. For example:
1. crack passwords by listening to keyboard sounds
2. determine what a computer user is doing by watching their mouse
hand, the light shining on the back wall of their office,
their keyboard motion, or their facial expressions
3. write a password search routine that is informed by all unencrypted
information on their computer drive, public information about them
found on the internet, etc
4. predict whether a corporation is going to announce a major transaction
by looking at public information about their executives travel behavior
5. use videos of poker player's faces to predict the strength of their hand
These kinds of projects have almost infinite freedom and room for a clever or creative student to do something truly new. The techniques used are different than the basic methods of mainstream cryptographic, but certainly related.
Ask the math department of your nearest univeristy for help.
m l
A true reasearch project might be somewhat of an undertaking, but
they can probably find something appropriate.
BTW - don't cheat yourself of trying Simon Singh's CD-rom
on cryptology: http://www.simonsingh.net/Shop_-_Crypto_CD-ROM.ht
-- A Mathematician is a machine for turning coffee into theorems. - Paul Erdös
If you're in the DC area, you can check out NSA's cryptol ogy museum</a>. I haven't been since I worked up there, but I remember it being far more in depth than you'd expect.
Mod point free since 2001
I was going to recommend reading Singh's book (see link) but it seems it was the course text so ...
Perhaps something a little less maths-y (or math-y if you're US-ian). She could study the use of PGP, the basics behind the cryptography, it's place in current email systems, historical export restrictions, why it's not used more, it's cipher strengths, how many nano-seconds it takes the NSA to crack it.
Ask Zimmerman to mentor it! Worth a shot?!
The Code Book: Simon Singh - http://tinyurl.com/d5zjs
Wikipedia entry on PGP - http://en.wikipedia.org/wiki/PGP
Just thought I'd toss in my few cents.
Bruce Schneier has a couple of essays that you might want to have your daughter check out. (Hopefully she already knows the info in the first, but....)
Here is his imput on how to get into the crypto field.
Why is crypto so hard .
If you or she aren't so keen on working with a local college/university math/CS department, I second the advice to hit up Phil Zimmermann. His site lists a number of ways to contact him. It also talks about his current project. (I found Mr. Zimmermann to be very gracious. I think the worst he would do is say no. More likely he would either agree or suggest someone as a alternative.)
Paul
The most obvious method is to encrypt the data but in order to selectively retrieve it becomes a problem (and over the years we do come back to our archives).
Another method I think might be great, is a way to just encrypt/protect the sensitive/identifying fields in a database and leave the statistical data unencrypted (that way you can have an archive/backup to run stats on but to get more sensitive info you need some sort of decryptioon technolog also if the machine/data was stolen the sensitive data would be safe.
an idea, good luck!.
"Enjoy what you're doing! If it becomes drudgery, you're doing it wrong!" - Jim Butterfield
She could research the early history of cryptology (i.e., World War 2). Although I haven't read the book yet, When Computers Were Human could serve as a starting point.
This may or may not be useful to you, but here's a list of current research projects my college (in the UK) is undertaking at the moment. It might give some idea of what's considered interesting areas in crypto:
# current
http://www.isg.rhul.ac.uk/research/projects.shtml
Personally, I think protocol analysis is pretty interesting, as the world gets increasingly networked up. Or investigate the practical effects of the recent breaks in hashing algorithms on other products that use the hashes (like digital signatures).
Start with the American Cryptogram Association , a non-profit organization of cryptographers that has been around for decades, dedicated to promoting the hobby and art of cryptanalysis. Alghough they concentrate on simple stuff (you have to start somewhere) the group is full of members that have "been around" and know their stuff!
Their resources page has links to everything you'll need to get started, from stuff covering cryptographic history to online lessons teaching you how analyze ciphers, and not just simple substitution ciphers either, but some pretty complicated ones (still a far cry from PGP though).
For a high school student a great and doable project would be to write software to crack CSS from scratch. The format is well documented on the web and cracking it via brute force is easily doable. A discussion of the weaknesses of CSS and the impact on the DVD industry would be doable as well. Plus this is something that has an impact that is more easily explained than MD5 collisions.
Lasers Controlled Games!
If she hasn't read them already, your daughter might find
David Kahn's
"The Codebreakers: The Comprehensive History of Secret Communication from Ancient Times to the Internet",
ISBN: 0684831309,
Bruce Schneier's
"Applied Cryptography: Protocols, Algorithms, and Source Code in C",
ISBN: 0471128457,
and
Alfred Menezes'
"Handbook of Applied Cryptography",
ISBN: 0849385237,
available for free online at http://www.cacr.math.uwaterloo.ca/hac/
to be of interest.
Research, by definition, means finding something out that no one else in the world has figured out. To do that, you need to understand more about some part of a given field than anyone else in the world. That's not fair to demand of a child, no matter how bright they may be.
Adults who study cryptography are on the "wow" scale of brilliant. They understand abstract math that most of us just can't learn even if we try our level best. In my undergraduate year, there was a math contest for people who were admitted to the mathematics faculty. It was deliberately hard: it was designed to tell if you were scholarship material: so the average score on it was about 25%. I scored a 23. My friend scored 95% on that test. He had the highest entrance marks of anyone that year; he graduated with Double Honours, and went on to do a PhD at Berkley. He's been actively interested in cryptography since the early 1990s. Despite all my friend's native genius, plus nearly a decade of formal training, he still doesn't find crypto research easy. Your kid, nice as he may be, doesn't stand a chance, and it's not fair to to expect him to.
Just let them play around with some of the existing mathematics: if they're as smart as you say, a formal proof of the RSA algorithm, and an analysis of poor key choice algorithms might be in order. Gently introduce him to some of the key points of the undergraduate math curriculum (obviously way to hard for most kids, but perhaps acceptable for a young budding genius). Perhaps an overview of group theory, and it's basic application to cryptography might demonstrate some interest, or some eliptic curve algebra, with explanations on how it's used in existing cryptographical implementations.
In any case, again, DO NOT expect a child to do mathematical research: it's horribly unfair. The only thing that's worse is those profs who put unsolved problems on their grad student's homework just to keep them humble.
4. predict whether a corporation is going to announce a major transaction by looking at public information about their executives travel behavior
That reminds me of something I read about predicting company mergers by new domain name registrations (whois).
You make the mistake of thinking you can educate the fundamental stupidity out of people. You can't.