Transcript Codebreaking in Everyday Life

Codebreaking in Everyday Life
John D Barrow
10 x 10 x 10 x 10 seconds  2.75 hours
Trap-door Operations
QUICK to encode
SLOW
to break
Big prime number x Big prime number = very large composite number
Are there enough Postcodes to go round?
The Pattern is AB3 4CD
262610102626 = 45,697,600 choices
UK population approximately 60,587,000
Approximately 26,222,000 households
and
28,500,500 expected by 2020
Enough for houses
But not for people!
National Insurance Numbers
(are not boring)



Eg pattern is NA123456X
262610101010101026 = 17.576 billion
Population of the world is about 6.65 billion and
maybe 9 billion by 2050
Stanley Milgram’s (Other) Experiment (1967)




Give many letters addressed to a Boston stockbroker to random people in
Omaha, Nebraska and Wichita, Kansas with a profile of stockbroker
They were to send them on to an acquaintance who they felt might know
more about the stockbroker, sign a roster and post a card (less junk mail in
those days!)
About 20% of Milgram’s letters reached the stockbroker
On average they took 6 reposting ‘steps’ to get there via the social network of
friends (6.6)
Small-World Networks
If you know 100 people and they know
100 others then you are just
one step away from 10,000 people
N steps away from 102(N+1) people
World population is 6.65 billion = 109.8
2(N+1) > 9.8 when N exceeds 4
“Six Degrees of Separation”
Friends of Friends of Friends
Are Important



Close links (friends and family) are a lot
like you and know the sorts of things and
people you know.
More distant acquaintances are more likely
to know things and people that you do
not.
The Prince and the pauper
Average Path Length

Erdös number of mathematicians
It’s a Small World After All
 Average Dist = (ln N / ln K) = 5.9
where N = total nodes and K = friends per node.
And K=30 and N = 108.8 = 10%  world population

Problems With Names
The Soundex Phonetic System (1918)












Keep first letter of the name
Delete a,e,i,o,u,h,y,w
Assign numbers to the rest of the letters
b,f,p,v = 1
c,g,j,k,q,s,x,z = 2
d,t = 3 and l = 4
m,n = 5 and r = 6
If two or more letters with same number are adjacent in original
name keep only the first
Keep only first 4 characters, make up to four with 00s if needed
John Barrow  Jn Br  J5 B6  J500 B600
Smith and Smyth  S530
Ericson, Erickson, Eriksen, Erikson  E6225. Robert, Rupert 
R163
Check-Digit Codes








To guard against transcription errors
Catch naïve fraudsters
Credit cards, tickets, passports, tax ID nos
889/899, 1112/112, 43/34,…..
Internal self-checking system to validate
numbers
Airline tickets 10 digits + one check digit which
is remainder after dividing by 7
4851913640 = 693130521 x 7 + 3
So ticket no. is 4851913640 3
Simple Errors Can Cause Problems
Type
a by b
ab by ba
abc by cba
aa by bb
a0 by 1a (a=2,3,..)
aca by bcb
Approx Frequency
79%
10%
1%
0.5%
0.5%
0.3%
Banking – What’s It All About?
IBANs
International Bank Account Numbers
GB82 WEST 1234 5698 7654 32
Country - cheque no - bank - sort – account no.
1. Move first 4 characters to the end
2. Replace letters by A=10, B=11,…Z=35
3. Interpret digit string as a decimal
4. Divide by 97
5. Valid IBANS give a remainder = 1.
eg
WEST 1234 5698 7654 32 GB82
 3214282912345698765432161182 = 1 mod 97
This is a valid IBAN
Moved
from front
Credit Cards and the Luhn Test


12 or 16 digits, for example:
4000 1234 5678 9314
L to R, double the digits in odd slots, add the two if
bigger than 9 (14  5 etc)
8 0 2 6 10 14 18 2
80261592
Sum = 33 + original digits in even slots
8+2+6+1+5+9+2+0+0+2+4+6+8+3+4 = 60
The total must be divisible by 10 for a valid card
Card number 4000 1234 5678 9010 fails (sum = 57)
Catches all single digit errors, most adjacent swops
(not 09/90 though)
Invented by Peter Luhn at IBM in 1954
Check validity
Fails !
Need to change the final check digit from 3 to 8 to validate the number
This is a necessary, but not a sufficient, condition for the card to be valid!
Universal Product Code
• Began in 1973 for grocery products
now used for most retailed goods
• 12 digit number represented by bars
for laser scanning
•Two strings of five between two single digits
6 44209 42095 7
Type of product
manufacturer
0,1,6,7,9 = any
2 = food by weight
3 = drugs, health
size/colour/model check digit
4 = sale items
5 = special offers/coupons
3 474370 01631 7
Check digit ?
Add digits in odd positions: 3 + 7 + 3 + 0 + 1 + 3 = 17
Multiply by 3: 3  17 = 51
Add digits in even positions: 51 + 4 + 4 +7 + 0 + 6 +1 = 73
Divide by 10: check digit is 10 minus the remainder = 7
ISBN-10
Multiply each digit by its position
from the right. Add and check digit must
make the sum divisible by 11.
If the remainder is 10 use X
eg for 0-19-280569-X the sum is 199 + X.
If X is 10 the total is 209 = 19  11
ISBN-13
Is like UPC but multiplies even
digits by
3 instead of odd ones. Check digit
must make sum divisible by 10.
International Mobile Equipment Identity IMEI




This is what you cancel when
your phone is stolen
Changing it is a criminal
offence
14 digits + check digit
The software version IMEISV
has 16 digits
49015420323751?
IMEI 4 9
0 1 5 4 2 0 3 2 3 7
Calculate
check
digit
5 1
4 18 0 2 5 8 2 0 3 4 3 14 5 2
=
=
9
5
Sum 4 9 0 2 5 8 2 0 3 4 3 5 5 2
?
Double
Every
Other
52
+
?
Check
Digit
Added
IMEI is 490154203237518
IMEI 4 9
0 1 5 4 2 0 3 2 3 7
5 1
?
Double
Every
Other
4 18 0 2 5 8 2 0 3 4 3 14 5 2


9
5
Sum 4 9 0 2 5 8 2 0 3 4 3 5 5 2
Sum must be divisible by 10
52+
8
The General Picture

Check digits are computed from a product code
a1a2a3a4…..an by multiplying by weights w1w2w3w4…..wn
and evaluating the dot product and remainder on dividing
by r
C = r - (a1 ,a2 ,a3 ,…an)(w1,w2,w3 ,…wn) = r - aw (mod r)





UPC : n = 12, w = (3,1,3,1…), r= 10
EAN-8: n = 7, w = (3,1,3,1…), r= 10
Airline: n = 10, w = (1,1,1,1…), r= 7
ISBN-10: n = 9, w = (10,9,8,7…,2,1), r= 11 and X =10
ISBN-13 and EAN-13: n = 12, w = (1,3,1,3…), r = 10
Sometimes You Don’t Need Numbers