| ITEC 120 |
| 2008fall |
| aaray, ejderrick, ibarland, jmdymacek |
|
|
|
home—info—labs—hws—exams
textbook—java.lang docs—java.util docs—archive
(double) 5 int m = 13; int n = 5; ((double) m) / ((double) n) |
Web traffic is sent on postcards. How to securely communicate your credit-card number to amazon, without any pre-arrangement? “Inconceivable!”?
Amazon might say on their web page:
Our public key pubKey = 37. If you want to send us a secret message privMsg (a two-digit number), multiply your secret number by our public key, and tell us the last two digits (only) of the result: That is, tell us (privMsg * pubKey) % 100. (We can name this result pubMsg.)Is announcing pubMsg secure, even if there are eavesdroppers? Let's try it! A volunteer: Choose your secret privMsg and write it down, without telling anybody. Compute pubMsg, and announce it. Can any of you eavesdroppers figure out the original message? (You want to just divide by 37, but how to do that in this world of mod-100 arithemetic?) The original privMsg was …
Teacher's trick: privMsg == ((pubMsg * privKey) % 100), where privKey = 73. Why 73? Because ((privKey * pubKey) % 100) == 1; That is, privKey is the multiplicative inverse of pubKey, mod 100. (It is total coincidence that 73 and 37 have the reversed digits, though that makes it easier for teachers to remember.)
Note that this used no pre-arrangement between the sender and the receiver. This is called “public key cryptography”, since eavesdroppers know as much about breaking the code as the sender.
If I offered you $1000000 challenge to find the student's particular privMsg by tomorrow, could you do it? Hint: does the term “brute-force approach” suggest a way to solve the problem? How long would this approach take? What if I used ten-digit (credit-card) numbers instead of 2-digit numbers? (That is, the public and private keys (37 and ??), as well as the modulus 100 would all be replaced with ten-digit numbers.) How long would it take then? What about 20-digit numbers?
You could break this code easily (w/o brute force),
if you could somehow divide by 37 mod 100.
(Or more precisely: find the multiplicative inverse of 37, mod 100.)
This would be a “back door” to the encryption algorithm,
if you knew a way to break it but other people thought it
unbreakable-in-practice.
Project: read about the extended Euclidean algorithm for calculating muliplicative inverses.
Break this code!
(If you take Discrete Math (ITEC122), this will be revisited.)
Although this particular scheme is easy to break with a bit of math knowledge (this Extended Euclidean algorithm), the real purpose of this example is to motivate how a public-key system is even conceivable.
double a = 93; double b = 1e18; double c = -b; double d = -300; a+b+c+d d+c+b+a |
Moral of the story: Beware, round-off error!Usually Round-off errors may seem small -- relegated to the 15th decimal place -- but be aware that sometimes small errors can add up. (Next time you fly home for thanksgiving, you might give some thought to whether the software controlling the plane is using doubles.)
In particular, watch out for problems involving both big and small numbers (like the a+b+c+d example). This can occur in problems where (literally) billions of small values are being added together for intermediate purposes. For example, suppose you want to compute the average salary of all six billion humans by adding up all the numbers and dividing by the number of humans. Even though the answer is nowhere near 1e16, might the intermediate sum-of-all-salaries get very large, and then when doing millions of operations like 1e16 + 1, you are getting millions of round-off errors which might accumulate.)
There are entire courses on Numerical Analysis — developing algorithms for doubles which have known, reasonable bounds on how big the total error might become.
Edict of Programming: When possible, using int is preferred to double.For instance, the price of an item is often best given in integer cents, rather than double dollars. This will avoid accumulation of small errors, as in 2.00-1.10 vs. 200-110. (We won't enforce this in grading for this class though.) But keep in mind, However, it's only appropriate for problems where you never have fractional amounts of cents; this may not be the case for (say) banking purposes.
Overflow refers to trying to use numbers that are bigger than the maximum number which can be stored (for doubles, Double.MAX_VALUE).
There is a complement to floating-point overflow, called underflow: we might try to compute numbers which are so closer to zero than the smallest possible double. Double.MIN_VALUE. Try evaluating Double.MIN_VALUE/2. As before, we have a trade-off between float vs double.
Aside: Java does have a way to do exact arithmetic, but it takes some extra typing:(This is a teaser to next week, when we'll talk about state, constructor-methods, and calling constructors with new.)
We mentioned, that casting raises the specter of silent overflow issues: If casting an int to a double, you are throwing away accuracy. But worse, if you cast a large double to an int, and that double is bigger than Integer.MAX_INT, Java chooses to let the cast silently succeed, with a wildly incorrect value!
(int)7e35 // Size of the universe, in nanometers... whereas 2billion nanometers ~ 6ft. (new Double(7e35)).intValue() // Same as casting (but written out). |
Beware numerical inaccuracies: (2.0 - 1.1 == 0.9), or ( (7.0/25.0)*25.0 == 7.0 ).
double x = 2.0 - 1.1; double y = 0.9; x == y // huh? That's an unexpected answer. How to debug? x // Oh, now it's clear what happened. |
Edict of Programming: Do not use == with doubles.So how do we see if two doubles are practically-equal? One immediate imponderable is “how close is close enough to be considered practically equal”? Well, for the moment2, let's say being within 0.001 is close enough: ((y-0.001 < x) && (x < y+0.001)) is a start. This amount 0.001 is often called the “tolerance” of the comparison.
Actually, we should look at an relative difference between two terms, rather than an absolute difference.
We have covered many topics over the last 3.5 weeks:
1 This is a preview: Just as there are built-in classes String and Math, there is also a class named Integer. The class Integer is a “wrapper class” for its little cousin, type int. We won't go into details, but just keep in mind that while int and class Integer are related, the primitive type int is not a class. ↩
2We'll later realize that we really should compare the relative size of the two numbers: 0.001 might be good for comparing people's height in inches, but not for the width of two hairs in inches. ↩
home—info—labs—hws—exams
textbook—java.lang docs—java.util docs—archive
| ©2008, Ian Barland, Radford University Last modified 2008.Oct.06 (Mon) |
Please mail any suggestions (incl. typos, broken links) to iba�rland  rad�ford.edu |
 |