|
|
Can I modify key.c and key.h? Absolutely. It provides a bare bones implementation of extended precision arithmetic that is sufficient for encrypt.c. You will likely need additional functionality for use with decrypt.c. You may also wish to optimize the bottleneck function, after you discover what it is.
How will the files be compiled? We'll remove decrypt.c and run "gcc226 *.c", then we'll remove brute.c and run "gcc226 *.c" again.
What value of C should I use in my submission? Submit the file keysize.h with C = 8. Do not put any other information in this file since we will replace it when grading. We'll only test decrypt.c with C = 4, 6, 8 and 10 if that simplifies your coding. We'll test brute.c with C = 4, 5 and 6. If you don't like hardwiring C into your .h file, it's possible to handle it dynamically and not use keysize.h.
How fast should my brute.c be? You should certainly be able to crack 4 character passwords. If it can't handle 5, try to think about what is the bottleneck and how you might improve it. Some simple ideas can be very effective. But, you can still move on to decrypt.c, and if there is time afterwards, work on improving the bottleneck since you'll likely have the same one in decrypt.c. If you have ideas but not enough time to implement them, describe them in your readme.txt.
How fast should my decrypt.c be? Our reference solution cracks 10 character passwords with rand10.txt using less than 100MB of memory in 1 minute on a 2.2 GHz Pentium 4 running Linux and 3 minutes on a 400 MhZ PowerPC running OS X. It's certainly a challenge to beat or match this; it's also possible to receive most of the credit even if your solution uses an order of magnitude more time and space.
How much memory should decrypt.c use? That's a difficult question. We will test on a system with 1GB main memory, but things definitely get sluggish when you use alot so don't be extravagant! Probably a limit of 250-500MB is more reasonable. If your system does not have enough memory, then you should plan not to exceed it. Your program will be judged on both time and memory usage, so your goal is to find a sweet spot that minimizes running time given a limited amount of memory.
How do I estimate memory usage? Your operating system provides an empirical method: on Unix type "top" (memory measure in kilobytes), on Windows NT look at the Task Manager (via Ctrl-Alt-Del and find the process ntvdm.exe). Use bytes (8 bits) as your basic unit along with the approximations: KB = thousand bytes, MB = million bytes, GB = billion bytes. You can also measure space analytically: use char = 1 byte, int = 4 bytes, pointer = 4 bytes.
My program runs quite a bit slower on degenerate tables like easy8.txt. Is this OK? Yes, we plan to test on random tables like rand8.txt since a password scheme based on such a degenerate table would be easy to break anyway. Use the degenerate tables for debugging.
|
|
Input. Here are some sample input files. You may also use generator.c to generate random test instances. It takes one command line input C, the number of characters per password.
Reference solutions. For reference, we provide our executable code for the two heuristics on Windows, Solaris, and OS X. Don't be alarmed or discouraged if our programs seem ridiculously fast!
|
|
You may use the following readme file template. Besides providing details about your implementation which are not clear from the comments within your source code, your readme.txt file should also contain:
|
|
These are purely suggestions for how you might make progress. You do not have to follow these steps.