• 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

    3.1.1 Subversion Subversion (SVN) is a version-control system, it allows peo- ple to work in the same time on the same files, which is what we need for a team project.Project Locker is a free (for less than 5 users) SVN provider, for more information about this provider cf. [6].

  2. Internet & Intranet Security

    aii.) Digital Certificate To obtain a digital certificate from a commercial Certificate Authority, in generally, the following steps will be carried out. The first step was to apply for a software publishing certificate (SPC). A software publisher's request for certification was sent to the LRA (CA).

  1. COMPUTER STUDIES INTERNET & INTRANET SECURITY

    A form of Denial of Service. (2,5) d) What are the ways to minimize the SYN attack? (4 marks) Ans: Increase the size of the in process queue which can provide additional space so that additional connection requests can be queued.

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

    A0i g(t)cos2?f0t + Asig (t),sin2?f0t i = 1, 2; 3,..., M (1.3) Where A0i and Asi are the of amplitude level-, that are obtained by mapping k-bit sequence into signal amplitudes, For example, Figure 1.2 shows a 16-QAM signal

  1. Security in a computing world.

    What they need to know before they launch an attack of any kind on the system. Initial study is very necessary to know how victim network is and what vulnerable service he/she running on their system. To make a perfect attack, attacker make sure he/she knows everything about the victim else they could end up with nothing.

  2. Wireless LANs, WLANs are now deployed at great pace both on company premises and ...

    While encryption, data changes to its original form depends on its algorithms. On the other hand if we run the same algorithm in reverse condition, then data again comes to its original form. Supposing some wants to send credit card information from one computer to another over the Internet, what

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

    It discusses various capabilities and features of the board. Moreover, this chapter also discusses about various functions that are required for the implementation of license plate recognition Chapter 5 presents the design results including simulation and DM6437 hardware implementation. It also discusses about various optimization techniques that are taken to improve the performance of the design.

  2. An Introduction to the IEEE 802.11p WAVE standard

    PKI uses certificates with private and public keys to authenticate. ECONOMIC | There is always an economic factor to take into account. If a new technology is not financially viable it will fail, regardless of its innovation and intuitiveness. It is crucial that WAVE provides a worthwhile expenditure for its

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