Computer Science > QUESTIONS & ANSWERS > Stanford UniversityCS 255hw2-sol CS255: Cryptography and Computer Security Winter 2010 Assignment #2 (All)

Stanford UniversityCS 255hw2-sol CS255: Cryptography and Computer Security Winter 2010 Assignment #2: Solutions

Document Content and Description Below

CS255: Cryptography and Computer Security Winter 2010 Assignment #2: Solutions Problem 1 Suppose we can find two message/hash pairs (M1; h(M1)) and (M2; h(M2)) such that M1 6= M2 and h(M1) = h(M2). Then, there exists ...

CS255: Cryptography and Computer Security Winter 2010 Assignment #2: Solutions Problem 1 Suppose we can find two message/hash pairs (M1; h(M1)) and (M2; h(M2)) such that M1 6= M2 and h(M1) = h(M2). Then, there exists two distinct Merkle hash trees T1 and T2 whose outputs are identical. We can find a collision for the compression function using a top-down side-by-side comparison of our two tree’s, looking across trees for a case where the outputs of f are the same, but the inputs differ. Starting at the root, suppose that either the first block or msg-length (thus height) of our trees differ, in this case, clearly we have found a collision in f, so we can stop our search. We can continue down examining the ith node of T1 and T2 and compare the inputs. If they differ, then we have found a collision for the compression function, and the procedure terminates. If not, we proceed to level i + 1 and repeat the same procedure. Note that since M1 6= M2, we cannot go through the entire tree without finding a collision. It follows that one can find a collision in the compression function. Problem 2 To construct a collision for the first hash construction with f1(x; y) = E(y; x) ⊕ y, choose any y and non-zero x so that y 6= (x ⊕ y). Let: x1 = D(y; x ⊕ y); y1 = y x2 = D(x ⊕ y; y); y2 = x ⊕ y So then: f1(x1; y1) = E(y; x1) ⊕ y = E(y; D(y; x ⊕ y)) ⊕ y = (x ⊕ y) ⊕ y = x f1(x2; y2) = E(y2; x2) ⊕ y2 = E(x ⊕ y; D(x ⊕ y; y) ⊕ (x ⊕ y) = y ⊕ (x ⊕ y) = x = f1(x1; y1) For the second compression function f2(x; y) = E(x; x) ⊕ y, choose any x1 6= x2, any y1, and let y2 = E(x1; x1) ⊕ E(x2; x2) ⊕ y1. Then f2(x2; y2) = E(x2; x2) ⊕ y2 = E(x2; x2) ⊕ (E(x1; x1) ⊕ E(x2; x2) ⊕ y1) = E(x1; x1) ⊕ y1 = f2(x1; y1) Problem 3 Collision resistance from discrete log. Let G be a finite cyclic group of prime oreder q. Let g be a generator of G. a. Suppose that u = gα for some x. Consider the following compression function h : Z2 q ! G defined by h(x; y) = gxuy. Show that any collision on h enables an attacker to compute the discrete log α.

[Show More]

Last updated: 4 months ago

Preview 1 out of 6 pages

Buy Now

Instant download

Preview of Stanford UniversityCS 255hw2-sol CS255: Cryptography and Computer Security Winter 2010 Assignment #2: Solutions

Buy this Document to get the Full Access Instantly

Provided by Students Who Aced it

We Verify Document Content to Gurantee Accuracy

Buy Now

Report Copyright Violation

Reviews( 0 )

QUESTIONS & ANSWERS

$11.00

Instant download

66

0

Document information

Connected school, study & course

About the document

Uploaded On

Jul 15, 2021

Number of pages

6

Written in

All

QUESTIONS & ANSWERS

Seller

Cheryshev

Member since 5 years

102 Documents Sold

Reviews Received

6

4

1

0

1

Additional information

This document has been written for:

Computer Science

QUESTIONS & ANSWERS

Uploaded

Jul 15, 2021

Downloads

0

Views

66

Document Keyword Tags

Recommended For You

Get more on QUESTIONS & ANSWERS »

Preview of CS 255 Introduction to Cryptography - Stanford University. Programming Assignment 1. Winte

Same Course Code Popular Match

$8.5

6 Pages

CS 255 Introduction to Cryptography - Stanford University. Pro...

Jul 20, 2026

Related document

Preview of CS 255 Introduction to Cryptography - Stanford University. Programming Assignment 1. Winte

Same Course Code Popular Match

$9.5

11 Pages

CS 255 Introduction to Cryptography - Stanford University. Pro...

Jul 20, 2026

Related document

Preview of WGU D075 OA EXAM NEWEST 2026 / WGU D075 WEB DEVEOPMENT FOUNDATIONS NEWEST 2026 ACTUAL E

Same Course

$13

14 Pages

WGU D075 OA EXAM NEWEST 2026 / WGU D075 WEB DEVEOPMENT FOUND...

Apr 01, 2026

Related document

Preview of CMU 10-601 Machine Learning Midterm Exam Solutions | Carnegie Mellon University

Same Course Popular Match

$11

17 Pages

CMU 10-601 Machine Learning Midterm Exam Solutions | Carnegie...

Apr 04, 2026

Related document

Preview of HIM 1103 FINAL EXAM with 100% verified solution

Same Course Popular Match

$10

16 Pages

HIM 1103 FINAL EXAM with 100% verified solution

Apr 03, 2026

Related document

Preview of AQA GCSE COMPUTER SCIENCE Paper 1 Computational thinking and programming skills – Python M

Same Course

$7

76 Pages

AQA GCSE COMPUTER SCIENCE Paper 1 Computational thinking and p...

Apr 22, 2026

Related document

Preview of AQA GCSE COMPUTER SCIENCE Paper 2 Computing concepts MAY 2025 Combined Question Paper and

Same Course

$7

55 Pages

AQA GCSE COMPUTER SCIENCE Paper 2 Computing concepts MAY 2025...

Apr 21, 2026

Related document

Preview of WGU D385 EXAM 2 2026 EXAM SCRIPT COMPLETE QUESTIONS AND SOLUTIONS GRADED A+

Same Course

$10

20 Pages

WGU D385 EXAM 2 2026 EXAM SCRIPT COMPLETE QUESTIONS AND SOLUTI...

Apr 19, 2026

Related document

Preview of WGU D385 EXAM 2 2026 FINAL PAPER COMPLETE REVISION QUESTIONS WITH FULL SOLUTIONS

Same Course

$10

25 Pages

WGU D385 EXAM 2 2026 FINAL PAPER COMPLETE REVISION QUESTIONS W...

Apr 19, 2026

Related document

Preview of CMU 10-601 Machine Learning Carnegie Mellon University final_solutions

Same Course Popular Match

$11

16 Pages

CMU 10-601 Machine Learning Carnegie Mellon University final_...

Apr 04, 2026

Related document

Preview of WGU D334 INTRO CRYPTOGRAPHY FINAL STUDY GUIDE 2026 QUESTIONS AND ANSWERS GRADED A+

Same Course

$10

67 Pages

WGU D334 INTRO CRYPTOGRAPHY FINAL STUDY GUIDE 2026 QUESTIONS A...

Apr 20, 2026

Related document

Preview of oftware Security Final Exam 2026/2027 – Comprehensive Q&A Study Guide

Same Course

$10.5

33 Pages

oftware Security Final Exam 2026/2027 – Comprehensive Q&A Stud...

Apr 10, 2026

Related document

Preview of ITE 152 EXAM 1, PRACTICE EXAM AND STUDY GUIDE NEWEST 2026 ACTUAL EXAM 140 QUESTIONS AND

Same Course

$13

28 Pages

ITE 152 EXAM 1, PRACTICE EXAM AND STUDY GUIDE NEWEST 2026 AC...

Apr 01, 2026

Related document

Preview of ITE 152 EXAM 2, PRACTICE EXAM AND STUDY GUIDE NEWEST 2026 ACTUAL EXAM 100 QUESTIONS AND

Same Course

$13

22 Pages

ITE 152 EXAM 2, PRACTICE EXAM AND STUDY GUIDE NEWEST 2026 AC...

Apr 01, 2026

Related document

Preview of Maternity HESI Test Bank 2026 / Combined RN Maternal Newborn Practice Questions & Answers

Same Category

$10.5

91 Pages

Maternity HESI Test Bank 2026 / Combined RN Maternal Newborn P...

Apr 21, 2026

Related document

Preview of HESI Mental Health Test Bank 2026 / Psychiatric Nursing Practice Questions & Answers / NCL

Same Category

$10.5

13 Pages

HESI Mental Health Test Bank 2026 / Psychiatric Nursing Practi...

Apr 21, 2026

Related document

Preview of HESI RN Leadership & Management Exit Exam 2024–2025 / Practice Test Bank Questions & Answe

Same Category

$12

21 Pages

HESI RN Leadership & Management Exit Exam 2024–2025 / Practice...

Apr 21, 2026

Related document

Preview of Computer Science H446/01: Computer systems Advanced GCE Mark Scheme for November 2020

Same Course Popular Match

$1

21 Pages

Computer Science H446/01: Computer systems Advanced GCE Mark S...

Apr 19, 2026

Related document

Preview of GCE Computer Science H446/02: Algorithms and programming Advanced GCE Mark Scheme for Nove

Same Course Popular Match

$1

23 Pages

GCE Computer Science H446/02: Algorithms and programming Advan...

Apr 19, 2026

Related document

Preview of OCR GCE Computer Science H446/02: Algorithms and programming Advanced GCE Mark Scheme for

Same Course Popular Match

$1

26 Pages

OCR GCE Computer Science H446/02: Algorithms and programming A...

Apr 19, 2026

Related document

More related documents below

Browse more QUESTIONS & ANSWERS

More From Cheryshev

View all Cheryshev's documents »

$11.00

Instant download

What is Scholarfriends

Scholarfriends.com Online Platform by Browsegrades Inc. 651N South Broad St, Middletown DE. United States.

Get to know us

About Us
Privacy Statement
Refund Policy
Terms and Conditions
Contact Us
Blog
HTML Sitemap
Sellers Directory (A–Z)

We are here to help

We're available through e-mail, Twitter, and live chat.
FAQ
Questions? Leave a message!

Follow us on

Instagram
Linktree
X (Twitter)

Useful links

Join our Subreddit

Solutions Manuals for Accounting, Business, Economics and Management Text Books. The Popular and the Latest.

Popular NURSING Test Banks

Sellers Directory (A–Z)

We accept

payment cards

Copyright © Scholarfriends · High quality services·