# MAGENTA

MAGENTA é uma cifra de blocos simétrica desenvolvida por Michael Jacobson Jr. e Klaus Huber para a Deutsche Telekom, que é uma companhia de telecomunicações alemã. O nome MAGENTA é um acrônimo de Multifunctional Algorithm for General-purpose Encryption and Network Telecommunication Applications, traduzindo, algoritmo multifuncional para criptografia de uso geral e aplicações de redes de telecomunicações. É uma cifra que foi submetida ao AES (Advanced Encryption Standard process), porém não passou da primeira etapa devida a uma falha criptográfica, tornando-se uma das cifras mais lentas em comparação com as submetidas.
O algoritmo que inspirou a criação do Magenta foi o DES (Data Encryption Standard). Pois, em dois de Janeiro de 1997, o NIST(Nacional Institute of Standards and Tecnology) anunciou que escolheria um sucessor para o DES, visto que este possuía uma chave, considerada pequena, de 56 bits. E consequentemente o tornava vulnerável a ataques de força bruta. No entanto, a competição possuía algumas regras, eram elas:
* O algoritmo teria de ser uma cifra de bloco simétrica
* Todo o projeto teria de ser público
* Deveriam ser admitidos tamanhos de chaves iguais a 128, 192 e 256 bits
* Teriam de ser possíveis implementações de software e hardware
* O algoritmo teria de ser público ou licenciado em termos não-discriminatórios.

## Desenvolvimento

O desenvolvimento do Magenta começou em 1990, partindo das regras da competição. A ideia era utilizar técnicas simples, de forma a tornar a implementação eficiente tanto para hardware quanto software. Para que isto fosse possível, foi utilizado uma estrutura borboleta para realizar difusão e exponenciação discreta em um campo finito.
Com o passar dos anos, a ideia de implementação em hardware foi analisada mais detalhadamente, e com a ajuda do especialista em hardware S. Wolter a estrutura borboleta foi trocada pela aleatória FHT, que possui a vantagem de fornecer estruturas idênticas para cada etapa. Mais algumas mudanças ocorreram quando uma análise do algoritmo foi feita por especialistas da companhia SIT, por volta de 1994.
O Magenta possui menos de 10kb de uso de memória estática, utiliza menos que 6kb da pilha. Para encriptar uma mensagem de 128-bit utiliza de 0 a 199 Kbps por segundo.

## Estrutura de funcionamento

O magenta é implementado utilizando a cifra de Feistel com 6 a 8 iterações. A Cifra de Feistel consiste em uma estrutura simétrica usada na construção de cifras de blocos. Ela é uma cifra iterada com uma função interna chamada função rodada.
Seja F a função rodada e sejam $K_{0},K_{1},...,K_{n}$ as subchaves para as rodadas 0,1,...,n, respectivamente.
Primeiro, divida o bloco em duas partes de mesmo tamanho,$(L_{0},T_{0})$ para cada rodada i = 0,1,...,n, então compute:
$T_{i}+1=L_{i}\oplus F(T_{i},K_{i})$
Como observado na figura, há uma única diferença entre a encriptação e a decriptação, inversão na ordem das subchaves durante a decriptação.

## Funcionamento do algoritmo

Seja $C={0,1}^{8}$ todos os vetores binários de 8-bits. Para x $\in$ C, escreveremos x = $(x_{7},x_{6},...,x_{0})$, e associamos cada byte com um inteiro em {0,1,...,,255} seguindo a fórmula $x_{7},x_{6},...,x_{0}->2x_{7}^{7}+2x_{6}^{6}+...+x_{0}$. Para todos x $\in$ B, defini-se: $f(x)=\alpha ^{x}x\neq 255$ $0x=255$
Magenta é uma cifra de bloco complexa. No entanto, o S-box tem uma estrutura simples. A S-box usada no Magenta é a seguinte:
1 2 4 8 16 32 64 128 101 202 241 135 107 214 201 247 139 115 230 169 55 110 220 221 223 219 211 195 227 163 35 70 140 125 250 145 71 142 121 242 129 103 206 249 151 75 150 73 146 65 130 97 194 225 167 43 86 172 61 122 244 141 127 254 153 87 174 57 114 228 173 63 126 252 157 95 190 25 50 100 200 245 143 123 246 137 119 238 185 23 46 92 184 21 42 84 168 53 106 212 205 255 155 83 166 41 82 164 45 90 180 13 26 52 104 208 197 239 187 19 38 76 152 85 170 49 98 196 237 191 27 54 108 216 213 207 251 147 67 134 105 210 193 231 171 51 102 204 253 159 91 182 9 18 36 72 144 69 138 113 226 161 39 78 156 93 186 17 34 68 136 117 234 177 7 14 28 56 112 224 165 47 94 188 29 58 116 232 181 15 30 60 120 240 133 111 222 217 215 203 243 131 99 198 233 183 11 22 44 88 176 5 10 20 40 80 160 37 74 148 77 154 81 162 33 66 132 109 218 209 199 235 179 3 6 12 24 48 96 192 229 175 59 118 236 189 31 62 124 248 149 79 158 89 178 0
Começando com 1 e movendo-se uma posição para a esquerda, obtemos a próxima entrada, quando 1 é deslocado para fora obtemos 101.
Depois, para todos os (x,y) $\in C^{2}$ : A(x,y) = f(x $\oplus$ f(y)). E PE(x,y) = (A(x,y),A(y,x)) = (f(x $\oplus$ f(y)),f(y $\oplus$ f(x))).
Para todos os ( x_0,...,x_15 ) \in C^16, faça: T(x_0,..,x_15) = $\prod (\prod (\prod (\prod (x_{0},...,x_{15}))))$, onde $\prod (x_{0},...,x_{1}5)$ é definido como $\prod (x_{0},...,x_{1}5)=(PE(x_{0},x_{8}),PE(x_{1},x_{9}),...,PE(x_{7},x_{1}5))$.
Para todos X=$(x_{0},...,x_{1}5)\in C^{1}6$ definimos: $X_{e}=(x_{0},x_{2},...,x_{1}4)eX_{0}=(x_{1},x_{3},...,x_{1}5)$, ou seja, $X_{e}$ possui os bytes de X com índice par e $X_{0}$ possui os bytes de X com índice ímpar.
$A^{j+1}(x_{0},...,x_{1}5)=T((x_{0},...,x_{7})\oplus A_{e}^{j},(x_{8},...,x_{1}5)\oplus A_{0}^{j})$
onde o valor inicial A^{(1)} = T(x_{0},...,x_{15}). Para fixar o número de rodadas r, nós definimos E^{r)(x_0,...,x_15} = C^(r)_e. Depois de uma análise em relação a efetividade do código, chegou-se a conclusão de que 3 rodadas são suficientes para proporcionar um código seguro. O bloco de cifras MAGENTA utiliza a cifra de Feistel, usando a função $E^{3)$ como base para a encriptação. Para $x=x_{0},...,x_{1}5\in C^{1}6ey=(y_{0},...,y_{7})\in C^{8}$, uma "rodada de Feistel" é definida como
$F_{y}(x)=((x_{8},...,x_{1}5),(x_{0},...,x_{7})\oplus E^{3_{x_{8},...,x_{1}5,y_{0},...,y_{7})})$
Seja $M=(x_{0},...,x_{1}5)\in B^{1}6$ seja um texto em claro de 128 bits. O algoritmo MAGENTA usa de seis a oito rodadas de Feistel, onde cada rodada utiliza uma parte diferente da chave. O algoritmo é dado por: $Enc_{k}(M)=F_{K}1(F_{K}1(F_{K}2(F_{K}2(F_{K}1(F_{K}1(M))))))$
$Dec_{k}(M)=V(Enc_{k}(V(M))),ondeV(x_{0},...,x_{1}5=(x_{8},...,x_{1}5),(x_{0},...,x_{7})$

## Criptoanálise

A criptoanálise é a técnica de se tentar descobrir o texto cifrado ou a lógica utilizada para encriptar a mensagem, sem ter conhecimento da chave.
Alguns tipos de ataque conhecidos são: Ataque por só-texto-ilegível, Ataque por texto legível conhecido, Ataque por texto legível conhecido, Ataque por texto ilegível escolhido e Ataque por força bruta.
Um dos tipos de criptoanálise mais antigos é por análise de frequência(ou Ataque por só-texto-ilegível). Ela consiste em analisar quantas vezes um determinado caractere aparece em um texto cifrado. E a partir dessa análise tentar descobrir qual caractere no texto em claro ele é, baseando-se nas probabilidades de que cada um tem de aparecer em um texto(de acordo com seu idioma). Por exemplo: em português, o carácter que mais aparece é o "a". E no inglês, é o "e".
No ataque por texto legível conhecido, o atacante conhece um pedaço do texto em claro e a qual parte do texto cifrado ele pertence. No entanto, não conhece a chave secreta k. No ataque por texto legível escolhido, o atacante "escolhe" o fragmento do texto que deseja descobrir, e assim, induz o receptor a decriptá-lo para ele.
No ataque por texto ilegível escolhido, o atacante escolhe uma parte do texto cifrado e a obtém no texto decifrado. Ele tem acesso somente ao algoritmo de decriptografia.
No ataque por força bruta, o atacante testa todas possibilidades de chaves possíveis para que ele consiga transformar uma mensagem encriptada em uma decriptada legível.

## Bibliotecas

As bibliotecas criptográficas CrypoAPI, JCA e OpenSSL implementam os algoritmos DES, Blowfish e mini-blowfish.