CS ASSIGNMENT 代写 : Secret Sharing Scheme For Image Encryption
With a ever increasing growth of multimedia applications, security is an important issue in communication and storage of images, and encryption is one of the way to ensure security. Image encryption has applications in internet communication, multimedia systems, medical imaging, telemedicine and military communications. In modern times, cryptography is considered to be a branch of both mathematics and computer science and is affiliated closely with information theory, computer security and engineering [1].
Many encryption schemes have been analyzed as possible solution systems. The basic ideas can be classified into three major types: position permutation [2]&[3], value transformation [4]&[5] and the combined form [6]. The Novel crypto system [7] uses randomly generated self invertible matrix as an encryption key for each block encryption. The resulting image from the algorithm is scrambled using a random matrix which is used as another secret key. This increases the secrecy of data. This method encompasses less computational complexity during decryption, as self invertible matrix [ 8 ] is used as key.
In the present paper an innovative technique for image encryption is proposed based on the random generation of polynomial. The new algorithm provides image encryption at two levels and hence security against the image is achieved at low computational overhead.
II. .Secret Sharing
Any method of dividing a secret into multiple (that is "n") participants is secret sharing. Each person receives a piece of the secret and the secret can be recovered by combining some or all of the shares. The secret is in the form of polynomial of degree "t-1", where "t "is the number of keys needed to get the secret (i.e., threshold value). The polynomial is expressed mathematically as follows.
F(x) = (1)
Where ai is a coefficient.
A. Secret process
A (t,n) threshold secret sharing scheme [1,2] is a cryptographic primitive used to distribute a secret "s" to "n" participants in such a way that a set of "t" or more participants can recover the secret "s" and a set of (t-1) or fewer participants cannot recover the secret "s".
The secret to be shared consists in text data , but also images can be considered. The first scheme to share images was due to Naor and Shamir [3] and it is called visual cryptography. It is based on visual threshold schemes t of n.
In this method, the coefficients a0, a1, …,a t-1 are randomly generated .The polynomial with the coefficients a0,a1, ….,a t-1 of degree (t-1) is represented as follows.
F(x) = a0 + a1 x + …..+ at-1 x t-1. (2)
Let the registered participant be "n" and let t < n, where t is a threshold value. Each participant has their own identity value IDi ( i = 1 to n ) . The function value of the polynomial for the input of participant's ID value is performed. Each function value is given to the corresponding participant. The function value for ID1 is share1; the function value for ID2 is share2 and so on. The sender sends share1 to the participant for ID1, share2 for ID2 and so on. The process is clear from the following flowchart.
Participant
For ID 1
Share
1
F(id1)
F(id1)
Share
2
Participant
for ID 2
F(id2)
. . .
Send to∙ . . ∙ .
. . . .
Participant
for ID n
Share
n
F(idn) ∙ ∙
Fig.1. Secret process flow chart
B. Polynomial generation
The first level of encryption is based on polynomial generation. The polynomial used in this level is generated at random and is of degree (t-1), where t is a threshold value. This could be expressed as follows.
F(x) = (3)
Where ai ia randomly generated coefficients.
III. Encryption Techniques
This technique is based on the following mathematical theorem.
CS ASSIGNMENT 代写 : Secret Sharing Scheme For Image Encryption
A. Theorem
A primitive root of a number is the one whose powers generate all the integers from 0 to p-1. That is if " a" is a primitive root of the primitive number "p" then the number "a mod p" , "a2 mod p" ….. "ap-1 mod p" are distinct and consists of integers from I through p-1 in some permutation.
B. Block construction
Two block matrix of size 6 x 6 are constructed from the theorem, When p = 7 and a = 3
a1 = ( 3 2 6 4 5 1)
when p = 7 and a = 5
b1 = (5 4 6 2 3 1)
The first block matrix "A" , a1 values are taken as the first row elements. Then add the adjacent elements of the first row to get the second row. Then the same procedure is applied with the second row to get the third row. And finally this procedure is applied with the fifth row to get the sixth row. Next apply this procedure with b1 values to get the second block matrix "B".
C. Zone Construction
The zone matrix " M " of size 216 x 216 is computed by using the following formulas.
For , , k = 1 , 2 … r.
Here t = 6, r = 3 ,
D. Transformation Matrix
The Transformation matrix has the following form.
M (X1) M (X2) M (X3 )
M (Y1) M (Y2) M ( Y3)
T =
M (Z1) M (Z2) M (Z3)
Where
X1 = ( S * A) Mod 256
X2 = ( S * B) Mod 256
X3 = (( S+1) * A) Mod 256
Y1 = ( (S + 2) * A) Mod 256
Y2 = ( (S + 2) * B) Mod 256
Y3 = ( (S + 3) * A) Mod 256
Z1 = ( (S + 4) * A) Mod 256
Z2 = ( (S + 4) * B) Mod 256
Z3 = ( (S + 5) * A) Mod 256
M(X) ïƒ Zone of X
S ïƒ Secret
A , B ïƒ Block matrix 6 x 6
E. Encryption Process
The Transformation matrix is XOR with the image matrix to get the encrypted image.
Original Image
Generate random polynomial
Form transformation matrix
Calculate Shares from the polynomial.
XOR Transformation matrix with the Image
Shares are sending to the corresponding participants
Encrypted Image
Fig.2. Encryption process flow chart
IV. DECRYPTION PROCESS
A. Reconstruction
Each participant accepts the share from the sender for reconstructing the secret. The participant who is having the identification value ID1 accepts the share y(1), the participant having the identification value ID2 receives the share y(2) and so on. Only t shares are enough to reconstruct the secret. The combiner receives t shares y(1), y(2) , …y(t) and the polynomial is reconstructed by using Lagrange interpolation formula . The Lagrange interpolation formula is given below.
F(x) = (5)
Where x1 , x2 , … xt are the identification values. F(x) ïƒ The reconstructed polynomial . t ïƒ Threshold value
B. Decryption process
The receiver reconstructs the polynomial from the shares of the participants using Lagrange interpolation formula. The mean value is evaluated from the reconstructed polynomial. Next the cipher text is decrypted with the mean value to get the original text. The following flowchart explains this.
Shares
Generate polynomial using Lagrange interpolation
Generate Transformation Matrix
Encrypted Image
XOR Transformation matrix with the Encrypted Image
Original image
Fig.3. Decryption process
V. ENCRYPTION Algorithm
Take the Original Image.
Randomly generate the polynomial of degree (t-1)
Construct the Transformation Matrix
XOR Transformation matrix with Image matrix
The threshold value t , identification value of the participants ID (ID1, ID2, …, IDn ) and the Encrypted image are given in public.
Calculate the function values F(ID1),F(ID2), ..F(IDn).
Send F(IDi) to the participant having the ID value IDi , where i = 1 to n.
VI. Decryption algorithm
Reconstruct the polynomial from "t" shares using Lagrange interpolation.
Construct the Transformation Matrix
XOR Transformation matrix with Encrypted Image matrix
Get the Original Image
VII. Sample Images
Fig 4: Leena Image Fig 5 : Encrypted Leena
Fig6: Cameraman Fig7: Encrypted Cameraman
Fig8: Gold hill Fig 9: Encrypted Gold Hill
VIII. Analysis
A. Histogram Analysis
Histogram analysis is employed to illustrate its superior confusion and diffusion properties in the encrypted data. The histogram of the plain image cameraman is shown in figure 10 and the histogram of the encrypted image is shown in figure 11. Comparing the two histograms, we find that histogram of encrypted image is fairly uniform and is significantly different from that of the original image, and that the encrypted images transmitted do not provide any suspicion to the attacker, which can strongly resist statistical attacks.
Fig10: Histogram For Cameraman
Original Image
Fig11: Histogram for Cameraman
Encrypted Image
B. Encryption quality analysis
The quality of image encryption [12] may be determined as follows:
Let F and F' denote the original image and the encrypted image respectively each of size M * N pixels with L grey levels. F(x,y), F' (x,y) € {0, 1,….,L-1} are the grey levels of the images F and F' at position (x,y) ( 0 ≤ x ≥ M-1, 0 ≤ Y ≥ N-1 ). Let HL (F) denote the number of occurrences of each grey level L in the original image F. Similarly , HL ( F' ) denotes the number of occurrences of each grey level L in the encrypted image F'. The encryption quality represents the average number of changes to each grey level L and is expressed mathematically as
Encryption Quality =
The encryption Quality of this proposed algorithm is computed and is tabulated as follows.
Table 1: Encryption Quality Table
Image
Size
Encryption
Quality
Leena
256 x 256
149.1953
Cameraman
256 x 256
252.6563
Gold Hill
512 x 512
713.7500
C. Information Entropy
The entropy H of symbol S can be calculated using the following equation.
H(S) = ,
Where p(si) represents the probability of symbol si.
If the information entropy of encrypted image becomes larger, image distribution of gray scale will be more uniform. By calculation, the information entropy of Leena encrypted image is equal to 7.9972, which means that information leakage in the encrypted process is negligible and the encryption system is secure from the entropy attack.
IX. Conclusion
In the new algorithm a polynomial is generated randomly. It is almost impossible to extract the original image in the proposed method even if the algorithm is known. In this algorithm, the image is encrypted after a number of rounds, which makes the computation more complex. Compared with the encryption schemes[10] based on the secret sharing , the size of the shares is far smaller with the size of the image.