The secret visual information sharing scheme
Good day, Habra users!
Visual cryptography [1] was first introduced by Moni Naor and Adi Shamir in 1994 [3]. It is used to encrypt an image or text represented as an image. The main idea of ​​the model of visual cryptography is to split the original image into several encrypted (“shadow” images, shadow images), each of which does not give any information about the original image except, perhaps, its size (image - a la “white noise” ). When overlaying encrypted images on each other, you can get the original image. Thus, decoding does not require special knowledge, high-performance computing, or even a computer (in case you print shadow images on transparent films). In the case of using this algorithm in computer systems, all parts of the image can be superimposed on each other using the logical operations AND, OR, XOR (or by setting a higher degree of transparency in the graphical editor). This technology is crypto-resistant due to the fact that when the source image is divided into multiple cipher images, it happens randomly.
Figure 1. Possible states of a pixel with a (2, 2) -visual secret exchange scheme
')
The application of such technologies is copy protection and authentication (copyright, watermarking ), tracking of electronic forms with remote voting, encryption of financial documents, access key management and password sharing.
Naor and Shamir demonstrated a ( k, n ) -visual secret exchange scheme, where the image was broken into n parts, so that anyone with any k parts could decipher it, while any k-1 parts did not allow no information about the content of the original image. When all k parts are superimposed on each other, we will see the original image [3].
In order to break the original black and white image into n parts, each pixel of the image is represented as a number of smaller parts ( subpixels ). The number of white and black parts is always the same. If a pixel is divided into two parts, then one white and one black block are obtained. If a pixel is divided into four equal parts, then we get two white and two black blocks.
Consider a (2, 2) -visual secret exchange scheme, i.e. the original image is divided into two shadow images, each of which is an image of white noise, but when applied it gives the original image. Each pixel of the original image will be divided into four parts, so if the size of the original image was M Ă— N , then the sizes of the shadow images will be 2M Ă— 2N .
Figure 1 shows that a pixel divided into four parts can have six different states.
If the pixel on the first layer has one position, the pixel on the second layer in turn can have two positions: identical or inverted to the pixel of the first layer. If the pixel of part 2 is identical to the pixel of part 1, then the pixel obtained by superimposing both shadow images will be half white and half black. Such a pixel is called gray or empty. If the pixels of part 1 and part 2 are opposite, then the pixel obtained as a result of the overlay will be completely black. It will be informational.
We describe the process of obtaining shadow images for the original image for the (2, 2) scheme: for each pixel of the original image, for the first shadow image , one of the six possible pixel states shown in Fig. 1 is randomly selected. The pixel state of the second shadow image is chosen identical or symmetrical the state of the pixel of the first “shadow”, depending on whether it is white or black, it was a pixel in the original image, respectively. Similarly, you can build any ( k, n ) visual scheme of secret exchange [3].
Theoretically, this algorithm can be effectively used to securely exchange messages over the network if the number of possible messages is not very large (for example, many different alarms). You can implement this exchange as follows.
Suppose that on the side of the message source there are only all the first shadow images from the pair (image 1), and on the side of the message receiver - only all the second images from the pair of shadow images (image 2). Each shadow image is completely random and, if it falls into the hands of the attacker separately (without the second image from the pair), it does not give any information. When one of the shadow images 1 is received, the receiver sequentially superimposes it on the images from its set and finds the first semantically loaded image-message (a particular alarm signal originating from the source of the messages).
A matlab function that splits the original binary image into two shadow “heads” using 4 (out of 6 possible, see Fig. 6) pixel states will look like this:
The
Below is the Matlab script code that demonstrates the work of the secret visual information sharing algorithm.
Below are the results of the operation of encoding and decoding the original "secret" image. Various operations of combining the resulting shadow images are considered: using XOR (Fig. 6), AND (Fig. 7) and OR (Fig. 8).
Figure 2. Original image
Figure 3. After image conversion to b / w
Figure 4. Shadow Image 1
Figure 5. Shadow image 2
Figure 6. Result for NOT (XOR (S1, S2))
Figure 7. Result for AND (S1, S2)
Figure 8. Result for OR (S1, S2)
The ( k, n ) -visual secret information sharing scheme is crypto-resistant until the k parts of the image fall into the hands of the intruder. If less than k parts are intercepted, then the decoding of the original image is impossible.
If in the process of using this system, a random approach to splitting pixels into blocks is fully observed, then visual cryptography offers absolute reliability and secrecy.
Here was considered the classical algorithm of visual cryptography. Today there are many improved models of this algorithm, for example, for encoding color images [4, 6], or schemes where, instead of shadow images in the form of white noise, semantically meaningful images are used [5], as well as visual cryptography schemes based on steganography technician [2, 7].
1. en.wikipedia.org/wiki/Visual_cryptography
2. en.wikipedia.org/wiki/%D0%A1% D1 ​​%82% D0% B5% D0% B3% D0% B0% D0% BD% D0% BE% D0% B3% D1% 80% D0% B0 % D1% 84% D0% B8% D1% 8F
3. M. Naor and A. Shamir. Visual cryptography. In EUROCRYPT'94. - Springer-Verlag Berlin 1995.
4. D. Jin, WQ Yan, and MS Kankanhalli. Progressive color visual cryptography. In Journal Of Electronic Imaging, 2005. — Vol. 14, Issue 3.
5. Feng Liu and ChuanKun Wu. Embedded extended visual cryptography schemes. - China, 2006.
6. YC Hou. Visual cryptography for color images. In Pattern Recognition, 2003.
7. Ritesh Murherjee, Nabin Ghoshal. Steganography based visual cryptography. - Berlin: Springer-Verlag, 2013.
Visual cryptography [1] was first introduced by Moni Naor and Adi Shamir in 1994 [3]. It is used to encrypt an image or text represented as an image. The main idea of ​​the model of visual cryptography is to split the original image into several encrypted (“shadow” images, shadow images), each of which does not give any information about the original image except, perhaps, its size (image - a la “white noise” ). When overlaying encrypted images on each other, you can get the original image. Thus, decoding does not require special knowledge, high-performance computing, or even a computer (in case you print shadow images on transparent films). In the case of using this algorithm in computer systems, all parts of the image can be superimposed on each other using the logical operations AND, OR, XOR (or by setting a higher degree of transparency in the graphical editor). This technology is crypto-resistant due to the fact that when the source image is divided into multiple cipher images, it happens randomly.
Figure 1. Possible states of a pixel with a (2, 2) -visual secret exchange scheme
')
The application of such technologies is copy protection and authentication (copyright, watermarking ), tracking of electronic forms with remote voting, encryption of financial documents, access key management and password sharing.
Algorithm of visual cryptography
Naor and Shamir demonstrated a ( k, n ) -visual secret exchange scheme, where the image was broken into n parts, so that anyone with any k parts could decipher it, while any k-1 parts did not allow no information about the content of the original image. When all k parts are superimposed on each other, we will see the original image [3].
In order to break the original black and white image into n parts, each pixel of the image is represented as a number of smaller parts ( subpixels ). The number of white and black parts is always the same. If a pixel is divided into two parts, then one white and one black block are obtained. If a pixel is divided into four equal parts, then we get two white and two black blocks.
Consider a (2, 2) -visual secret exchange scheme, i.e. the original image is divided into two shadow images, each of which is an image of white noise, but when applied it gives the original image. Each pixel of the original image will be divided into four parts, so if the size of the original image was M Ă— N , then the sizes of the shadow images will be 2M Ă— 2N .
Figure 1 shows that a pixel divided into four parts can have six different states.
If the pixel on the first layer has one position, the pixel on the second layer in turn can have two positions: identical or inverted to the pixel of the first layer. If the pixel of part 2 is identical to the pixel of part 1, then the pixel obtained by superimposing both shadow images will be half white and half black. Such a pixel is called gray or empty. If the pixels of part 1 and part 2 are opposite, then the pixel obtained as a result of the overlay will be completely black. It will be informational.
We describe the process of obtaining shadow images for the original image for the (2, 2) scheme: for each pixel of the original image, for the first shadow image , one of the six possible pixel states shown in Fig. 1 is randomly selected. The pixel state of the second shadow image is chosen identical or symmetrical the state of the pixel of the first “shadow”, depending on whether it is white or black, it was a pixel in the original image, respectively. Similarly, you can build any ( k, n ) visual scheme of secret exchange [3].
Theoretically, this algorithm can be effectively used to securely exchange messages over the network if the number of possible messages is not very large (for example, many different alarms). You can implement this exchange as follows.
Suppose that on the side of the message source there are only all the first shadow images from the pair (image 1), and on the side of the message receiver - only all the second images from the pair of shadow images (image 2). Each shadow image is completely random and, if it falls into the hands of the attacker separately (without the second image from the pair), it does not give any information. When one of the shadow images 1 is received, the receiver sequentially superimposes it on the images from its set and finds the first semantically loaded image-message (a particular alarm signal originating from the source of the messages).
Matlab algorithm implementation
A matlab function that splits the original binary image into two shadow “heads” using 4 (out of 6 possible, see Fig. 6) pixel states will look like this:
function [S1,S2] =getShdwImg(Img) % S1 S2 (Img) % % [m,n] = size(Img); % :) S1= zeros(2*m,2*n); S2= zeros(2*m,2*n); % - . 1 % : for i=1:m-1 for j=1:n-1 r = randi(4); if(Img(i,j)==1) switch r case 1, S1(2*i,2*j)=1; S1(2*i+1,2*j)=1; S1(2*i,2*j+1)=0; S1(2*i+1,2*j+1)=0; S2(2*i,2*j)=1; S2(2*i+1,2*j)=1; S2(2*i,2*j+1)=0; S2(2*i+1,2*j+1)=0; case 2, S1(2*i,2*j)=0; S1(2*i+1,2*j)=0; S1(2*i,2*j+1)=1; S1(2*i+1,2*j+1)=1; S2(2*i,2*j)=0; S2(2*i+1,2*j)=0; S2(2*i,2*j+1)=1; S2(2*i+1,2*j+1)=1; case 3, S1(2*i,2*j)=0; S1(2*i+1,2*j)=1; S1(2*i,2*j+1)=1; S1(2*i+1,2*j+1)=0; S2(2*i,2*j)=0; S2(2*i+1,2*j)=1; S2(2*i,2*j+1)=1; S2(2*i+1,2*j+1)=0; case 4, S1(2*i,2*j)=1; S1(2*i+1,2*j)=0; S1(2*i,2*j+1)=0; S1(2*i+1,2*j+1)=1; S2(2*i,2*j)=1; S2(2*i+1,2*j)=0; S2(2*i,2*j+1)=0; S2(2*i+1,2*j+1)=1; end else switch r case 1, S1(2*i,2*j)=1; S1(2*i+1,2*j)=1; S1(2*i,2*j+1)=0; S1(2*i+1,2*j+1)=0; S2(2*i,2*j)=0; S2(2*i+1,2*j)=0; S2(2*i,2*j+1)=1; S2(2*i+1,2*j+1)=1; case 2, S1(2*i,2*j)=0; S1(2*i+1,2*j)=0; S1(2*i,2*j+1)=1; S1(2*i+1,2*j+1)=1; S2(2*i,2*j)=1; S2(2*i+1,2*j)=1; S2(2*i,2*j+1)=0; S2(2*i+1,2*j+1)=0; case 3, S1(2*i,2*j)=0; S1(2*i+1,2*j)=1; S1(2*i,2*j+1)=1; S1(2*i+1,2*j+1)=0; S2(2*i,2*j)=1; S2(2*i+1,2*j)=0; S2(2*i,2*j+1)=0; S2(2*i+1,2*j+1)=1; case 4, S1(2*i,2*j)=1; S1(2*i+1,2*j)=0; S1(2*i,2*j+1)=0; S1(2*i+1,2*j+1)=1; S2(2*i,2*j)=0; S2(2*i+1,2*j)=1; S2(2*i,2*j+1)=1; S2(2*i+1,2*j+1)=0; end end end end The
getShdwImg function splits the source image as shown in Fig. 1, with the only difference is that in Matlab binary images, the black pixels of the image are zero, and the white, respectively, are equal to one.Below is the Matlab script code that demonstrates the work of the secret visual information sharing algorithm.
close all % RGB- biImg = imread('nordavind_logo.jpg'); biImg = rgb2gray(biImg); level = graythresh(biImg); % (Otsu) biImg = im2bw(biImg,level); % figure(1) imshow(biImg); title(['Original binary image']); % [S1,S2] =getShdwImg(biImg); % figure(2) imshow(S1); title(['Shadow image S1']); % figure(3) imshow(S2); title(['Shadow image S2']); % % figure(4) % imshow(or(S1, S2)); % imshow(and(S1,S2)); imshow(~xor(S1, S2)); % “~”(NOT) , , title(['Superimposed image']); results
Below are the results of the operation of encoding and decoding the original "secret" image. Various operations of combining the resulting shadow images are considered: using XOR (Fig. 6), AND (Fig. 7) and OR (Fig. 8).
Figure 2. Original image
Figure 3. After image conversion to b / w
Figure 4. Shadow Image 1
Figure 5. Shadow image 2
Figure 6. Result for NOT (XOR (S1, S2))
Figure 7. Result for AND (S1, S2)
Figure 8. Result for OR (S1, S2)
Conclusion
The ( k, n ) -visual secret information sharing scheme is crypto-resistant until the k parts of the image fall into the hands of the intruder. If less than k parts are intercepted, then the decoding of the original image is impossible.
If in the process of using this system, a random approach to splitting pixels into blocks is fully observed, then visual cryptography offers absolute reliability and secrecy.
Here was considered the classical algorithm of visual cryptography. Today there are many improved models of this algorithm, for example, for encoding color images [4, 6], or schemes where, instead of shadow images in the form of white noise, semantically meaningful images are used [5], as well as visual cryptography schemes based on steganography technician [2, 7].
Links
1. en.wikipedia.org/wiki/Visual_cryptography
2. en.wikipedia.org/wiki/%D0%A1% D1 ​​%82% D0% B5% D0% B3% D0% B0% D0% BD% D0% BE% D0% B3% D1% 80% D0% B0 % D1% 84% D0% B8% D1% 8F
3. M. Naor and A. Shamir. Visual cryptography. In EUROCRYPT'94. - Springer-Verlag Berlin 1995.
4. D. Jin, WQ Yan, and MS Kankanhalli. Progressive color visual cryptography. In Journal Of Electronic Imaging, 2005. — Vol. 14, Issue 3.
5. Feng Liu and ChuanKun Wu. Embedded extended visual cryptography schemes. - China, 2006.
6. YC Hou. Visual cryptography for color images. In Pattern Recognition, 2003.
7. Ritesh Murherjee, Nabin Ghoshal. Steganography based visual cryptography. - Berlin: Springer-Verlag, 2013.
Source: https://habr.com/ru/post/177355/
All Articles