### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Tpc Games CS 349

GPA 3.89

### View Full Document

## 37

## 0

## Popular in Course

## Popular in ComputerScienence

This 8 page Class Notes was uploaded by Jordon Hermiston on Thursday October 29, 2015. The Class Notes belongs to CS 349 at Wellesley College taught by Staff in Fall. Since its upload, it has received 37 views. For similar materials see /class/230943/cs-349-wellesley-college in ComputerScienence at Wellesley College.

## Reviews for Tpc Games

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/29/15

Spurious keys and uniciTy disTance ApplicaTion of enTropy 65349 Cryptography DeparTmenT of CompuTer Science Wellesley College Key equivocaTion 0 We apply The re5ulTs from lasT lecTure To esTablish relaTionships beTween The enTropies of componenTs of a crypTosysTem o The condiTional enTropy HKIC is called The key equivocaTion and is a mea5ure of how much informaTion abouT The key is revealed by The cipherTexT UniciTy disTance 102 Remember me Theorem HX Y HY HXIY Corollary Hle S HX wiTh equaliTy if and only if X and Y are independenT UniciTy disTance 103 HKIC HK HP HC Observe ThaT HK P C HCIK P HK P Now The key and plainTexT uniquely deTer mine The cipherTexT Thus HCIK P O and HK P C HK P HK HP In a similar fashion HK P C HK C PuTTing This all TogeTher39 HKIC HK C HC HK P C HC HK HP HC The luTTer equaliTy since K and P are independenT UniciTy disTance 104 An old old friend 0 Le 03a b wi139h Pra14Prb 34 K K1 K2 K3 wi139h PrK1 12 and PrK2 PrK3 14 and C 1 2 3 4 wi139h encryp rion func rions given by The following encryp rion ma rrix a b K 1 2 K2 2 3 K3 3 4 0 We had calculafed HP 081 HK 15 and HC 185 The previous Theorem Tells use Thai HKIC is approxima rely wha r Unicify disfance 105 Spurious keys 0 Suppose Oscar Carol39s 0 There are only me meaningful plainfex r s139rings river and arena corresponding To keys F 0 evil rwin ob rains a cipher rexf s rring WNAJW which has been ob rained by encryp rion using a shif r cipher an Oscar cannof know which is correc139 and which is a spurious key Unicify disfance 106 Bounding spurious keys 0 Our goal is To prove a bound on The expecTed number of spurious keys To do so we seek a definiTion of The enTropy per eTTer of a naTuraI language L denoTed HL 0 HL should be a measure of The average informaTion per eTTer in a meaningful sTring of plainTexT o UniciTy disTance 107 EnTropy of a language L Suppose L is a naTuraI language The enTropy of L is defined To be The quanTiTy H Pquot H L 11111 quotam 1 and The redundancy of L is defined To be RL 1L logzl Pl 108 UniciTy disTance Redundancy 0 Empirical sTudies esTimaTe ThaT for The English language 10 3 HL 315 ThaT is The average informaTion conTenT in English is abouT one and a half biTs per leTTer Using 125 as our esTimaTe of HL gives a redundancy of abouT 075 In oTher words English is 75 redundanT a UniciTy disTance 109 ngrams of plain and cipher TexT 0 Given probabiliTy disTribuTions on Kand 0quot we can define The induced probabiliTy disTribuTion on Cquot Define Pquot and Cquot To be The random variables representing ngrams of plain and cipher TexT respecTively o UniciTy disTance 1010 CalculaTing The number of spurious keys 0 Given yE Cquot define Ky K E K Elx E Tquot such ThaT Prx gt O and eKx y o ThaT is Ky is The seT of keys K for which y is The cipherTexT The number of spurious keys is IKyI 1 and The average number of spurious keys is E EPriyiam I l EPriyJImM EPriy EPriyilmn l Uni ciTy disTance 1011 Key equivocaTion revisiTed From our firsT Theorem HKICquot HK HPquot HCquot Using The esTimaTe HPquot nHL n1 Rlog2 I03 we obTain HKICquot HK HPquot HCquot HK quot1 RL 92 WI HCquot HK n log2 I03 RLlog2 I03 HCquot 2HK n log2 I03 RLlog2 I03 n log2 ICI HK 39 quotRLlogz iqji Here we used The Ted ThaT HCquot 5 nlog2 ICI and assumed ThuT ICI I PI Uni ciTy disTance 10 12 Key equivocaTion and spurious keys NexT we r elaTe HKICquot To The number of spurious keys HK IC 2PryHK Iy yECquot s EPry10g2Ky yEC slogz EPriyile yEC log 1 Jensen39s inequaIiTy snuck inTo The compuTaTion Where UniciTy disTance 10 13 Combining The Two inequaliTies We have 10g2 1 2 HK IC 2 HK nRL 10g2 ITI In The case where keys are chosen equipr obably HK Iogz I KI and we have 10g2 1 2 10g2 I KI nRL 10g2 ITI mm 10 7 g2 T RL gt IEKI S I PI RL Which maximizes HK UniciTydisTance 1014 A bound for spurious keys Suppose 03 C K E D is a crpyTosysTem where ICI WI and keys are chosen equiprobably LeT RL denoTe The redundancy of The underlying language Then given a sTring of cipherTexT of lengTh n where n is sufficienle large The expecTed number of spurious keys saTisfies 7 gt K S 7 n I q IHRL UniciTy disTance 10 15 UniciTy disTance o The uniciTy disTance of a crypTosysTem is defined To be The value of n denoTed by n0 aT which The expecTed number of spurious keys becomes zero ThaT is The average number of cipherTexT required for an opponenT To be able To uniquely compuTe The key given enough compuTing Time a SeTTingquot To zero in i K Squot Z I r and solving for n gives a esTimaTe for The uniciTy disTance no z 10g2 QC RL 10g2 rPI UniciTy disTance 10 16

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "I made $350 in just two days after posting my first study guide."

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.