• Join over 1.2 million students every month
  • Accelerate your learning by 29%
  • Unlimited access from just £6.99 per month

IT Security. In this practical we focus on digital signing based on RSA and ElGamal. We also look at the Digital Signature Standard and the use of hashing when signing.

Extracts from this document...

Introduction

SIT392 PUBLIC KEY CRYPTOGRAPHY   2011  TRIMESTER 1

PRACTICAL SESSION 4 SOLUTIONS

In this practical we focus on digital signing based on RSA and ElGamal. We also look at the Digital Signature Standard and the use of hashing when signing.

A. Using RSA to sign.

1. Alice uses an RSA scheme based on the modulus 1081357. She only signs messages with 6 digits (base 10) and odd numbers, but only Alice knows this. You receive a signed message claiming to be from her which is 725226. You look up her public key: 17. Is the message really from Alice?

Solution.

To retrieve the message, you compute 725226^17 mod (phi(n))= mod (1079260) and get

1029556. So the message is not from Alice and could not have been computed using her private key. You should check with Alice in any case.

B. Using El Gamal to sign.

1. Alice derives an El Gamal signature scheme using p = 5023, α = 5 and y = 5a = 3796. Her computations yield β = 5r ≡ 2294 and γ = (444 – 2294 a)r-1  ≡ 3740, where m = 444 is the message. Determine if Bob should accept the signed message as valid.

Solution.

Bob checks by computing 5444 (mod 5023) ≡ 4678

...read more.

Middle

Solution.

Bob will do the same verification he did in part B above:

Bob checks by computing 5927 (mod 5023) ≡ 600.

and also yββγ (mod p) ≡379612871287225 ≡ 600 .

Since the two computations match, bob will assume that Alice signed this message.

2. Oscar has captured the message m = 487 along with the signed pair β = 1723 and γ = 7045 in Alice’s scheme with p = 7481, α = 6 and y = 5979. He checks that m-1 exists mod (p-1) and since it does, proceeds to choose his own message m1= 2222.

(a) Show how Oscar can now fraudulently attach Alice’s signature to this message.

Solution.

  1. m-1 = 983 (mod7480). He computes t = m1 m-1 (mod p – 1) = 66 and

γ1 = tγ (mod p – 1) = 1210.

Oscar now uses the CRT to compute a solution β1 to the system

                x ≡βt (mod p – 1) = 1518

                x ≡β (mod p) = 1723.

We can use Maple to do this for us:

with(numtheory);

 > chrem([1518,1723],[7480,7481]);

image01.png

Oscar now sends (54425998, 1210) and 2222 to Bob.

(b) Why might Bob suspect that Oscar has used this attack?

Solution (b) Bob will notice that one of the values he receives is larger than the prime p used.

C.

...read more.

Conclusion

= gn mod p since gq mod p = 1.

6. The above lemma is followed by a proof that the DSS verification actually works.

THEOREM.  If M= M, r= r, and s= s in the signature verification, then v = r.

Read this through and understand the steps.

Solution. Proof: We have w = (s)-1 (mod q) = s-1 (mod q) and u1 = ((SHA-1(M))w) (mod q) = ((SHA-1(M))w) (mod q) and u2 = ((r)w) (mod q) = (rw) mod q.

Now y = gx (mod p), so that by the lemma, v = ((gu1 yu2) mod p) (mod q) = ((gSHA-1(M)w yrw) mod p) (mod q) = ((gSHA-1(M)w gxrw) mod p) (mod q) = ((g(SHA-1(M)+xr)w) mod p) (mod q).

Also s = (k-1(SHA-1(M) + xr)) (mod q).

Hence w = (k(SHA-1(M) + xr)-1) (mod q) so  (SHA-1(M) + xr)w mod q = k (mod q).

Thus by the lemma, v = (gk mod p) mod q = r= r.

7. Appendix 5 of the same document gives an example where p is 512 bits. Look through the example and see what kinds of computations are needed to work with this size of prime modulus.

...read more.

This student written piece of work is one of many that can be found in our University Degree Computer Science section.

Found what you're looking for?

  • Start learning 29% faster today
  • 150,000+ documents available
  • Just £6.99 a month

Not the one? Search for your essay title...
  • Join over 1.2 million students every month
  • Accelerate your learning by 29%
  • Unlimited access from just £6.99 per month

See related essaysSee related essays

Related University Degree Computer Science essays

  1. Implementation of Path Finding Techniques in Homeland Security Robots

    Robots are now being used extensively to rescue survivors from hazardous environments. For e.g. when there is a fire robots can be made to go through the fire and rescue. A serious limitation is the lack of sensors that can be mounted on the robots.

  2. The project explains various algorithms that are exercised to recognize the characters present on ...

    L2 cache is configured in an "ALL SRAM" mode means a part of it was not configured as cache. Thus in order to configure L2 partly as cache and partly as RAM, one needs to configure the Gel file that is available with the video preview code provided by Texas Instrument.

  1. A bucketing framework for Database security

    We naturally used Eclipse (cf. [2]) to make our development. Moreover to facilitate the project we used a free Subversion hosting provider Project Locker (cf. [6]) and to control and check our work we used JUnit tests [5]. We naturally used as well the JavaDoc in order to facilitate the reading of the code2 .

  2. An Introduction to the IEEE 802.11p WAVE standard

    design models, the reality is that in 2012 not everyone is going to be driving a new car from BMW or Chrysler[3], or a new car from any manufacturer for that matter. Plentiful cars on the road will still be old, so even when this technology is rolled out fully,

  1. Methods and technology used in Computer Forensics

    3.2.1 NIST CFTT, FS-TST & NSRL NIST (National Institute of Standards and Technology) is a US Department of Commerce body responsible for the measurement of standards in relation to advances in technology. It is a non regulatory body, but its high levels of funding and quality scientists and engineers has made NIST one of the world's most respected standards institutes.

  2. Data Warehouse Security

    Privacy Laws To reduce the concern of unauthorized use of personal data, national Governments have passed laws establishing requirements in the management of customer information. By understanding such laws, establishment of appropriate security measures in the data warehouse environment can be made.

  1. Secure Shell technology, SSH Communications Security has been involved in research and development ...

    Cryptanalysis is the study of mathematical methods which are used in attempting to defeat cryptographic techniques. Cryptology means the study of cryptography and cryptanalysis. * Basic Cryptographic Algorithms The method of encryption and decryption is called a cipher. Some cryptographic methods rely on the secrecy of the encryption algorithms; such

  2. So in order to understand what the main areas where organisation should be aware ...

    * Coordinated Scans Probing a few target systems from a single IP within a certain amount of time will usually turn on the alarm of the intrusion detection systems. We have already discussed a way to try to bypass this - using slow scans.

  • Over 160,000 pieces
    of student written work
  • Annotated by
    experienced teachers
  • Ideas and feedback to
    improve your own work