• 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. A bucketing framework for Database security

    It becomes more and more usual - particularly when the data retrieval are needed from any Internet access point - to call for a external application service provider to outsource the data center operation. Encryption is usually supported to protect the data and in- dexing is commonly used to make

  2. Internet & Intranet Security

    the bottom CA and end-users subscriber. Certificate Trust List (CTL) was a list of signed trusted Certificate Authority (CA) certificates. Certificate trust was that a certificate was part of the CTL or that the CTL contained a trusted certificate from anther CA that was part of the certificate chain. aii.)

  1. COMPUTER STUDIES INTERNET & INTRANET SECURITY

    A SYN attack floods this smaller queue with connection requests. When the target system replies, the attacking system does not respond and leaves the connection request in the smaller queue for time expiration. By filling up this queue with bogus requests, the target system can no longer to accept legitimate requests.

  2. Modulation.A modulation is a process by which an information signal is converted to a ...

    1.1 Modulation A quadrature-amplitude-modulated (QAM) signal uses two quadrature, carriers, cosine function (cos2? f0t), and sine function (sin 2?f0t), each of which is modulated by an independent sequence of information bits. The simplest block diagram of the QAM modulator is shown in Figure 1.1 Picture 1.1: Canonical QAM Modulator The

  1. Security in a computing world.

    attacks to gain the knowledge how different attack works and how they can be disaster for victim. I would be researching on what are the common methods of attack and how hacker and cracker use those methods to be successful in their mission.

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

    Algorithms like Defragmentation, Resizing, Character Localization and Template matching were tested both in Visual studio and on TI's DAVINCI EVM320DM6437 platform and are written in the advance C and C++ programming language. 1.4. Organization of Report Chapter 2 contains basic concepts of the smallest image (Pixel)

  1. An Introduction to the IEEE 802.11p WAVE standard

    users, as well as being an attractive proposition for those who will have to implement it. To gain the market penetration necessary to make WAVE economically viable, it is suggested that it will have to support standard internet protocols. In other words, general internet access and family orientated applications will

  2. Data Warehouse Security

    The data must be available to authorized users when needed, while keeping track of the actions performed on it (Elson and Le Clerc, 2005). A rising need When data warehouses were first established in the late 1980s, protection against unauthorized access was simpler.

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