Crypto-Imagery Image & Video Y. Benlcouiri, M. C. Ismaili, A. Azizi Laboratory of Arithmetic, Scientific Computing and Applications, Faculty of Science, Mo- hamed First University, Oujda, Morocco. (benlcouiriy, mcismaili, abdelmalekazizi)@yahoo.fr Abstract. This paper is structured on securing of storage, transmission and the traceability of digital images. It consists in the design of the cryptographic algo- rithms appropriate to the case of fixed and moving images. In this sense, we have introduced two approaches that is different in the synthe- sis of confusion and diffusion on using the principles of substitu-tion and/or transposition to secure JPEG and MPEG format. 1 Introduction Before the emergence of the web and the expansion of the need for sharing of multimedia documents in many types of applications, name- ly, tele- medicine, IPTV, Video on Demand (VOD), video conferencing or private military ... the need for security became a major issue. To this effect, the computer security is called to its indispensable tool which is the crypto in order to guarantee those documents a secure in content. The algorithms of modern cryptography such as AES, DES or RSA... Show all of the problems facing the image coding by loss of information. In effect, the loss of a single bit of an encrypted message during compression deteriorate the entire block when its decryption. Therefore, the encrypted images by these algorithms cannot undergo the procedures of irreversible compression, and have other problems of slow, even when it is to encrypt the images in their compressed form. In addition, the crypto in his native approach to encrypt all of the doc- uments does not seem suited to the particular case of pictures and vid- eo, especially, when it comes to the applications in real time. As well, to respond to these problems, we have proposed solutions that are based on linear applications of the type (ax+b), to perform op- erations of substitution and/or dissemination. What guarantee a pro- cessing time more optimal than the standards of encryptions, which are based on power calculations such as the RSA, EL-Gamal ¦ or those who clutter the numbers of rounds such as the DES, AES etc. On the other hand, for cohabitation between the crypto and compression algorithms by loss of information, in their format the most popular JPEG and MPEG. In this sense, we propose to retain only the operations of trans- position on the blocks already processed by the JPEG algorithm. This leaves each of the algorithms operate independently of the processing space of the other. In effect, the JPEG performs loss of information at the block level, and then the algorithm that we propose does not affect their content. In addition, it changed their location. However, the trans- position seems to be well suited to this type of problems, except that its security is not based only on the complexity of the algorithm used, but given on semantic vulnerabilities related to the reconstruction of a puz- zle, without having recourse to the encryption algorithm and/or those of decryption. To illustrate the solutions that we propose. In what follows, we sit in a first time, the preliminary mathematics needed for the construction of our two crypto-systems. And then, we will present the foundation of each of our two cryptographic applications and their implementation algorithmic. Then, we will describe their mode of use on images in the JPEG format and the MPEG video. As well as the results obtained af- ter the application of each of them. Finally, we will conclude our chap- ter by a general balance on the different algorithms proposed. 2 The Affine-Crypto Since all the operations in crypto manifest themselves as either a sub- stitution is a transposition or a mix of the two, we present below one of the crypto-systems developed in the work of this thesis. These works are based on the affine application which allows you to carry out, at the time, substitution and permutation. The difference between these two operations resides in the space on which they operate. While the substitution is restricted to the number of symbols in the space of the representation, transposition, as to it, is related to the length of the message. We propose the application of these two operations on the images and video, using the applications following again: 2.1 The affine Substitution: Buried since the early work of Al-Kindi by the analysis of the frequen- cies of the occurrence of the letters in the languages. The mono- substitution (substituting mono-alphabetic) no longer constituted that a problem of transcoding on the frequency of occurrence of the latter, even if we would have a chain of substitution from a true randomiza- tion. That said, in the case of images, is there a rule of the appearance of the colors? Without forgetting that the image is regarded as the universal language that can express his miles words in the different languages that exist... This observation led us to carry the principle of the affine en- cryption since the ring toward the one in order to adapt it to the case of the image. Encryption:. Either the number of symbols in the space of the representation (all distinct). It is called substitution refines the application , which at a given, match an image . The function S is définie as follow: Or: The pair represents the key of the substitution such that and; Then that is the value of the plaintext message, which will be replaced by its corresponding . Decryption:. The reverse proxy is an application that has to vacation to give each its clear value . OF or the formal definition of is: Or: is the inverse of the in , that was calculated by the algorithm of Euclid extended such that , and the decryption key is the pair. 2.2 The Transposition affine: It is based on the problem of the reconstruction of the puzzle, which belongs to the family point unresolveable, and the unconditional safety that can offer any system of transposition. In what follows, we will in- troduce the affine function on which rests our system of transposition. Encryption. Either the length of the message, and the transposition affine is ob- tained by the application of the function defined below on each of the indices of the initial vector to find its correspond- ing. Or: is the key (encryption) transposition avecet, And is the index of a component of the message which will be rearranged in a new location. Decryption. The rearrangement (or decryption) of the message in its format non- noisy, is achieved by applying the transpose function reverse on each of the indices of the blocks of the encrypted message. This function is defined as follows: Or: is the inverse of in , that was calculated by the algorithm of Euclid extended, such as: Thus the decryption key is the pair. Key Space : The key space is considered as one of the essential pillars on which rests the safety of crypto-symmetric systems. In this sense, the key space of each of the applications presented below is of possible keys in the general case. In conclusion:  The substitution: is an application that operates on a space of a fixed size in the case of images. What rounded the number of keys to  The transposition: in se mode of operation the number of keys varies depending on the size of the message (or image) and remains in its general format , such as the num- ber of blocks in the message.  Mixed=alternative+transposition: incorporate the two appli- cations would lead to the multiplication of the number of keys in each of them either of These results do that condemn the dictated of Shannon in these work on the information theory, which considers that the substitution does not offer a good level of security, but may increase one of a system by transposition. 2.3 Affine Algorithm In this section, we present the implementation of the mathematical con- cepts of the crypto-affine under algorithmic form. The algorithms of encryption and decryption are formulated as follows: Encryption Algorithm:. Variable:  Number of symbol s in the space of the representatives,  The length of the message ,  The encrypted message ; Entry:  Message (or image),  The surrogate key with and,  The keyof permutation and ; Beginning :  For i=0 to not of 1 up to // * Substitution & Transposition * //  End for Finish. The inverse algorithm which performs the phase of the decryption is of the following form: Algorithm for decryption:. Variable:  Number of symbol s in the space of the representatives,  The length of the message ,  The encrypted message ; Entry:  Message (or image),  The surrogate key with and,  The key to swap and; Beginning :  For i=0 to not of 1 up to // * Substitution & Transposition * //  End for Finish. Complexity. The complexity of each of the algorithms in terms of the speed of exe- cution is of two multiplication operations and two other of addition (resp subtraction), more than a single assignment operation, which will turn the execution of our method in operations such as is the size of the message. OF or the confirmation of the polynomial complexity of our algorithm which is in . However, the crypto-affine, seems to be well adapted to the particular case of pictures and video. In effect, the capacity of the data processing is the asset of the substitution in the color world. In addition, it remains vulnerable to the number of combinations that can generate an applica- tion affine. In effect, this last is proportional to the number of possible keys either of keys . Knowing that the number of possible combinations of a set and. The question asked is: Is there an application that allows you to pull a combination among the combinations that exist? To answer this question, we have put in place a new solution based on the algebraic structure defined in the section that follows. 3 New form algebraic To remedy the problems of the crypto-affine as regards the number of combinais he can offer, we have proposed a new function which is capable of generating all possible permutations on a set of elements, either of combinations. This function is defined on a structure of type in which our function is constructed as follows: Or the couple has for conditions: et. The number of possible keys on this function is equal to that of a affine application, since the conditions on the parameters (or keys) remain the same, or the possible keys. The major difference between this new function and the ap- plications affines presented in section crypto-affine, is evident in the fact that composed of , which on the contrary applications affine or whose composed always remains on the case possibles. The function with respect to it, under certain condi- tions on the keys, allows us to go further to generate more that permutations, see all the combinations of a set of elements. Therefore, there is a condition to satisfy on the keys, so that the re- sult of the composed either: , This means that the compound is outside the suites accessed by a single application. For this to be possible, the conditions to be respected on the couples of keys which are succeeding each other in a composition of the form are: Either Example of use on the body: Fig. 1. Illustrative Example of the application of the function B to generate the permuta- tions. Key Space. The difference between the space of keys on the applications further affine and the new application resides in the fact that, the applications further refinement (crypto-affine) are limited to the number of possible keys, whereas, on the method, the number of keys is relatively linked to the number of composed of , if it assumes that: , With and which satisfy the conditions presented above. In this case the number of keys is of ; Has this fact, the number of keys can be input according to the num- ber and type of compound used ; simple in the case , or complex . As well the number of keys can achieve the use of all the composite applications possible, either of )( ( )× ) which is greater than !. That said, the number of keys is greater than the number of possible messages. Thus, it highlights the conditions of a crypto-perfect system which satisfies the conditions of Shannon on a simple system of transposition (or broadcast). In effect, all systems of permutation are of unconditional safety (the entropy of the message clear = the entropy of the encrypted message). We add through the offered function the fact that the number of possible keys is greater than the number of possible messages. After having justified the theoretical basis for this type of applica- tions and demonstrated its usefulness on the example above. In what follows, we will present the algorithms that use this feature to build the same synthesis than that presented in crypto-affine, and which consists of operations of substitution and transposition. 3.1 Algorithm The procedures for encryption and decryption that use the new construc- tion are formulated as follows: Encryption Algorithm: The algorithm provides, below, allows you to perform, at the time, the operations of substitution and transposition. The two couples of keys and shall be used, respectively, to perform the substitution and transposition by the application of the function. The key neutral ( 1.0 ) can be used when one wants to ignore one of the two operations. Variable:  Number of symbol s in the space of the representa- tives+1,  The length of the message+1,  The encrypted message ; Entry:  Message (or image),  The surrogate key with and,  The key to swap and; Beginning:  For i=1 to not of 1 up to // * Substitution & Transposition * // If ( ) Then If ( ) Otherwise End of If Otherwise If ( ) Then Otherwise End of If  End for Finish. Algorithm for decryption. The inverse function of the encryption process is defined as follows :