An Identity based Encryption Schemebased on Quadratic Residues Introduction:In Public KeyCrypto system, it is required to know the Public Key of Receiver to encrypt themessages.
So that receiver can decrypt the message using his/her own privatekey. This system needs to maintaindirectories which holds Public Keys of each user. To eliminate the need ofmaintaining such directories, this paper suggests computing the public keyusing receiver’s identity such as Email address.
However, implementation ofsuch system which is secure and practical, is difficult. The system uses QuadraticResidues modulo a large composite integer. 2 What is Quadratic Residues?”If m and a are coprime integers, then ais called a quadratic residue modulo mif the congruence has a solution. “1 Congruent Meaning:” ifm divides (a – b). Also, if and only if a mod m = b mod m. For Example, 15 mod 4 = 3 mod 4 = 3.” 3 Jacobi symbol:”The Jacobisymbol, written (n/m) is defined for positive odd m as Where ” 4 Functionality:The system has anauthority that generates public modulus M, which is universally available (Publiclyknown).
M = PQP and Q are keptPrivate (Secret) by Authority, also they are congruent to 3 mod 4. System alsouses secure hash function, which is publicly available. If Alice wants toreceive a message from Bob, she gets Private Key from authority by presentingher own identity.
On the other end, Bob uses Alice’s public identity (key) toencrypt the data for Alice. Here, Public key Dictionary is not Required. Description of System:Hash function isapplied to the string representing Alice’s identity and a value has been calculated by authority, such thatJacobi Symbol for all values of a. This is universally known process, anyone knowing Alice’sidentity can calculate . One who does not know the factorization of M,can calculate Jacobi Symbol easily.
As then,awill be square modulo of both P and Q. Hence,a is square modulo of M. Also, P and Q arecongruent to 3 mod 4,Thus, a or-a will be Quadratic Residues moduloP and Q.
Only authoritycan determine the square root of modulo Mand provide it to Alice. Here, we call it rWhere, If Bob wants tosend data to Alice, he will generate a Transport key and perform Symmetric KeyEncryption using that key. Then, he sends it to Alice bit by bit. Let’s say, isthe single bit of transport key, coded as +1or -1. Bob will choose a value t at a random modulo M, such that Jacobi Symbol Then, he sends to AliceAlicerecovers the bit as follows,Also,it follows Jacobi Symbol Here, Alice knows the value of r, using that she will calculate valueof Bob need todouble up the Key data as he is not aware whether Alice uses root of a or -a. He will select random t to send bits, and send Thereis no way to avoid sending this extra amount of data. 2 PracticalImplementation Aspects:System is notvery much expensive in terms of computation. If transport key is K bits long,then Alice need to compute K Jacobi Symbols and Bob will need to compute Kdivisions mod M and K Jacobi Symbols.
Issue:· Each bit ofTransport key requires size up to M for bandwidth. · Bob Does not knowwhether Alice uses square root of a or -a, hence, he must double key data. Use:· It can be used inoffline applications such as Email. Security Analysis:· Factorization ofM can be used to break the system. Also, M and r values need to compute inshared fashion, so that master secret can’t be on single location.· This scheme isvulnerable against Chosen Ciphertext Attack. Attacker can modify each bit oftransport key at a time while transmission and by observing the decryption,attacker can compute transport key bit. It has been suggested to add someredundancy to transport key, so that a small part of randomly chosen messagewill be decrypted correctly.
If the entire decrypted message is not correct,then system will give an error of invalid message output.