What keeps your password safe?
A good service provider (e.g. a bank) will not store customers' passwords. The reason is simple. If someone hacks into the computer of the servic provider, he would easily get the passwords should they be stored in the computer.
How to prevent this from happening?
Your bank does not store your password, but rather a hashed version. When you log onto your bank account, the bank's computer compares the hashed version of the password you type in with the entry stored in its hashed-password profile.
The hashed version, denoted by H, is actually a function of your password, let's call it input x.
To make the hashed version secure, the function H(x) should have the following properties:
1. For any input x, it should be easy to compute H(x) ;
2. Given H(x) , it should be computationally infeasible to find x(inverse function);
3. All values produced by H, say y, should have the same bit-length; (y, if different from your password x are "collisions"). This is to prevent some different bit-length input y, which produces H to gain access.
4. It should be computationally infeasible to find y that collides with x, i.e. H(x) = H(y).
Note: "computationally infeasible" means it would take the fastest computers more than a human life to carry out the procedure to completion. That is to say, even someone hacks into the stored H(x) , he would not be able to obtain your password, x.
Sunday, November 22, 2009
The Numbers Behind Numb3rs - DNA Profiling
DNA profiling (also called genetic fingerprinting) is a technique to identify individuals on the basis of their respective DNA profiles. Although 99.9% of human DNA sequences are the same in every person, enough of the DNA is different to distinguish one individual from another. DNA profiling uses repetitive ("repeat") sequences that are highly variable, called variable number tandem repeats (VNTR). VNTRs loci are very similar between closely related humans, but so variable that unrelated individuals are extremely unlikely to have the same VNTRs.
a. The FBI's CODIS System: based on 13 loci (including Virginia's 8-loci); total of 3,000,000 in the database;
b. Virginia Division of Forensic Science: based on 8 loci; total of 101,905 offender profiles (as of November 1999) in the database;
c. Arizona: based on 13-loci; total of 65,000 offender profiles in the datase.
The probability that someone would match a random DNA sample at any one site (locus, pl. loci) is roughly 1 in 10.
The probability that someone would match a random DNA sample at 8 loci is __________.
The probability that someone would match a random DNA sample at 9 loci is __________.
The probability that someone would match a random DNA sample at 13 loci is __________.
Case Study: USA v. Raymond Jenkins
At first, the DNA profiling was done against Virginian database of 8-loci. The likelihood of an accidental match is roughly 101,905 x 1/100,000,000 = 1/1,000. Considered quite high, Jenkins was released from custody.
Later, more evidence was found and another DNA profiling was performed against the FBI's database of 13-loci. The likelihood of an accidental match is roughly 3,000,000x 1/10,000,000,000,000 = 1/3,000,000. Considered extremely rare, Jenkins was then arrested and charged with second-degree murder.
The Database Match Calculation:
Suppose an DNA sample is sent to Arizona for DNA profiling with 13 loci and 65,000 DNA profiles in the database,
what is the probability of there being a 9-locus match?
Given that the probability that someone would match a random DNA sample at any one locus is roughly 1 in 10.
(1) For 9-locus DNA profiling, the probability for a 9-locus match is _________________.
(2) Out of 13 loci, there are ________________ different ways of having 9-locus match.
(3) Hence, finding a match on any 9 loci of the 13 is 715 / 1,000,000,000.
(4) If any one profile is picked in the database, the proability of a second profile not matching on 9 loci is 1- 715/10^9.
(5) The probability of all 65,000 entries not matching on 9 loci is (1- 715/10^9)^65,000. Using Binomial Theorem, this is approximately 1- 65,000x715/10^9.
(6) The probability of there being a 9 loci match is thus 1- (1- 65,000x715/10^9) = 65,000x715/10^9 = 0.05 = 5%.
In fact, an actual analysis of the Arizona database uncovered 144 individuals whose DNA profiles matched at 9 loci, 144/65,000 = 0.22% (differed from the theoretical 5%, why?), one pair matched at 11 loci and one pair matched at 12 loci. The 11 and 12 -locus matches turned out to be siblings, hence not random.
Extension: Brithday Problem (23, >50%). In a class of 40, the probability of two students share the same birth date is as high as 85%. Surprised?!
a. The FBI's CODIS System: based on 13 loci (including Virginia's 8-loci); total of 3,000,000 in the database;
b. Virginia Division of Forensic Science: based on 8 loci; total of 101,905 offender profiles (as of November 1999) in the database;
c. Arizona: based on 13-loci; total of 65,000 offender profiles in the datase.
The probability that someone would match a random DNA sample at any one site (locus, pl. loci) is roughly 1 in 10.
The probability that someone would match a random DNA sample at 8 loci is __________.
The probability that someone would match a random DNA sample at 9 loci is __________.
The probability that someone would match a random DNA sample at 13 loci is __________.
Case Study: USA v. Raymond Jenkins
At first, the DNA profiling was done against Virginian database of 8-loci. The likelihood of an accidental match is roughly 101,905 x 1/100,000,000 = 1/1,000. Considered quite high, Jenkins was released from custody.
Later, more evidence was found and another DNA profiling was performed against the FBI's database of 13-loci. The likelihood of an accidental match is roughly 3,000,000x 1/10,000,000,000,000 = 1/3,000,000. Considered extremely rare, Jenkins was then arrested and charged with second-degree murder.
The Database Match Calculation:
Suppose an DNA sample is sent to Arizona for DNA profiling with 13 loci and 65,000 DNA profiles in the database,
what is the probability of there being a 9-locus match?
Given that the probability that someone would match a random DNA sample at any one locus is roughly 1 in 10.
(1) For 9-locus DNA profiling, the probability for a 9-locus match is _________________.
(2) Out of 13 loci, there are ________________ different ways of having 9-locus match.
(3) Hence, finding a match on any 9 loci of the 13 is 715 / 1,000,000,000.
(4) If any one profile is picked in the database, the proability of a second profile not matching on 9 loci is 1- 715/10^9.
(5) The probability of all 65,000 entries not matching on 9 loci is (1- 715/10^9)^65,000. Using Binomial Theorem, this is approximately 1- 65,000x715/10^9.
(6) The probability of there being a 9 loci match is thus 1- (1- 65,000x715/10^9) = 65,000x715/10^9 = 0.05 = 5%.
In fact, an actual analysis of the Arizona database uncovered 144 individuals whose DNA profiles matched at 9 loci, 144/65,000 = 0.22% (differed from the theoretical 5%, why?), one pair matched at 11 loci and one pair matched at 12 loci. The 11 and 12 -locus matches turned out to be siblings, hence not random.
Extension: Brithday Problem (23, >50%). In a class of 40, the probability of two students share the same birth date is as high as 85%. Surprised?!
Friday, November 20, 2009
Amazing Art - Upside Down
Below are the collections of "The Upside-Downs of Little Lady Lovekins and Old Man Muffaroo" by Gustave Verbeek in 1905. Yes! 1905!
What do you see from the drawing on the left?
Another example here. The cartoon can be read upright and upside down.
What do you see from the drawing on the left?...
...
...
...
...
An island with trees and a man in a boat?
A bird with someone in its mouth?
See coloured version here.
Another example here. The cartoon can be read upright and upside down.
One more example here. (Click View upside down )
Scott Kim's Inversions - Symmetry
You may not have heard of him. But you will surely be amazed by his works.
Scott Kim is an American puzzle and computer game designer, artist, and author. He created hundreds of other puzzles for magazines as well as thousands of puzzles for computer games.
He had an early interest in mathematics, education, and art, and attended Stanford University, receiving a BA in music, and a PhD in Computers and Graphic Design. In 1981, he created a book called Inversions, words that can be read in more than one way. His first puzzles appeared in Scientific American in Martin Gardner's "Games" column. He is one of the most well-known masters of the art of ambigrams.
Selected recent works of Scott Kim:
Joy to the World (The snowflakes are special.)
Alphabet Tessellation (Amazing!Click on any letter to start tessellating.)
Fantasy (Scott Kim is true someone.)
GALLERY of his recent works
CLASSROOM ACTIVITIES for teachers
CLASSROOM GALLERIES of inversions by students
LINKS to other ambigram artists
CLASSROOM ACTIVITIES for teachers
CLASSROOM GALLERIES of inversions by students
LINKS to other ambigram artists
DIE DIE MUST ...
Fair 6-sided dice are used in the questions.
(1) Throwing 1 die, what is the probability of getting a 6?
(2) Throwing 2 dice, what is the probability of getting a sum of 6?
(3) Throwing 3 dice, a sum of 10 is more likely or a sum of 9?
Do NOT peep the answers before you attempt the questions!
No... No... No... PEEPS YET...
...........................................................................................................
.
.
.
.
.
.
............................................................................................................
Answers:
(1) 1/6
(2) Tabulate the results, you can see there are 5 times of sum 6 out of the total 36 outcomes. So it is 5/36.
(3) 9: (621) (531) (522) (441) (432) (333)
10: (631) (622) (541) (532) (442) (432)
Do they have the same chance? Not really.
Let's see. For example, (6 2 1) there are 6 different ccombinations 126, 162, 216, 261, 612, 621.
If we do that, we find that there are 27 ways of getting 10 and 25 ways of getting 9. Hence, 10 is more likely to appear.
(1) Throwing 1 die, what is the probability of getting a 6?
(2) Throwing 2 dice, what is the probability of getting a sum of 6?
(3) Throwing 3 dice, a sum of 10 is more likely or a sum of 9?
Do NOT peep the answers before you attempt the questions!
No... No... No... PEEPS YET...
...........................................................................................................
.
.
.
.
.
.
............................................................................................................
Answers:
(1) 1/6
(2) Tabulate the results, you can see there are 5 times of sum 6 out of the total 36 outcomes. So it is 5/36.
(3) 9: (621) (531) (522) (441) (432) (333)
10: (631) (622) (541) (532) (442) (432)
Do they have the same chance? Not really.
Let's see. For example, (6 2 1) there are 6 different ccombinations 126, 162, 216, 261, 612, 621.
If we do that, we find that there are 27 ways of getting 10 and 25 ways of getting 9. Hence, 10 is more likely to appear.
Subscribe to:
Posts (Atom)
