[zeikson]

Hola.

Estoy intentando resolver un problema pero me estoy liando. Podéis ayudarme?

Dice lo siguiente:

Se ha recibido el siguiente mensaje, cifrado con un criptosistema lineal:

{20, 62, 2, 43, 138, 11, 33, 94, 19, 34, 115, 94, 109, 103, 133, 108, 6, 56, 119, 66, 107, 48, 108, 114, 40, 105, 13, 25, 120, 30}

También se sabe que el mensaje se ha cifrado con la clave:

\( \begin{bmatrix} 1 & 5 & 8 \\ 7 & 15 & 74 \\ 8 & a & 1 \end{bmatrix} \)

de la cual se ha borrado una entrada, que escribiremos 'a'. Para que valores de 'a' la clave da un criptosistema lineal? Cual es el mensaje descifrado si se recuerda que empezaba por la letra 'A'?

Dado un alfabeto aleatorio (A-->1, B-->2,...,Z-->26, a-->27, ..., z-->53, ...), alguien puede indicarme como solucionarlo?
Gracias.

[Luis Fuentes]

Hola

 No es que sepa demasiado de Criptografía, pero el cifrado con matriz que conozco requiere un alfabeto con un número conocido de signos. ¿Qué significa alfabeto aleatorio? ¿Cuántos símbolos tiene?.

Saludos.

[zeikson]

Creo que el problema se refiere a este alfabeto.

{ "A"->1,"B"->2,"C"->3,"D"->4,"E"->5,"F"->6,"G"->7,"H"->8,"I"->9,"J"->\
10,"K"->11,"L"->12,"M"->13,"N"->14,"O"->15,"P"->16,"Q"->17,"R"->18,\
"S"->19,"T"->20,"U"->21,"V"->22,"W"->23,"X"->24,"Y"->25,"Z"->26,"a"->\
27,"b"->28,"c"->29,"d"->30,"e"->31,"f"->32,"g"->33,"h"->34,"i"->35,\
"j"->36,"k"->37,"l"->38,"m"->39,"n"->40,"o"->41,"p"->42,"q"->43,"r"->\
44,"s"->45,"t"->46,"u"->47,"v"->48,"w"->49,"x"->50,"y"->51,"z"->52,\
"Ç"->53,"ç"->54,"Ñ"->55,"ñ"->56,"0"->57,"1"->58,"2"->59,"3"->60,"4"->\
61,"5"->62,"6"->63,"7"->64,"8"->65,"9"->66,"Á"->67,"À"->68,"Â"->69,\
"Ä"->70,"É"->71,"È"->72,"Ê"->73,"Ë"->74,"Í"->75,"Ì"->76,"Î"->77,"Ï"->\
78,"Ó"->79,"Ò"->80,"Ô"->81,"Ö"->82,"Ú"->83,"Ù"->84,"Û"->85,"Ü"->86,\
"á"->87,"à"->88,"â"->89,"ä"->90,"é"->91,"è"->92,"ê"->93,"ë"->94,"í"->\
95,"ì"->96,"î"->97,"ï"->98,"ó"->99,"ò"->100,"ô"->101,"ö"->102,"ú"->\
103,"ù"->104,"û"->105,"ü"->106,"."->107,","->108,";"->109,":"->110,"+\
"->111,"-"->112,"*"->113,"/"->114,"="->115,"_"->116,"¡"->117,"!"->118,\
"¿"->119,"?"->120,"("->121,")"->122,"["->123,"]"->124,"{"->125,"}"->\
126,"|"->127,"@"->128,"#"->129,"€"->130,"·"->131,"$"-\
>132,"%"->133,"&"->134,"\\"->135,"\"->136," ' "->137,"`"->138," "->0}

Saludos.

[Luis Fuentes]

Hola

 Vale. Veo que tienes 139 caracteres. Si no me equivoco los pasos serían los siguientes.

 - Calcula el determinante de la matriz clave módulo 139.

 - Será una matriz válida cuando el determinante es no nulo.

 - Despues calcula la inversa de la matriz módulo 139.

 - Agrupa el código de 3 en 3 y multiplica por esa inversa. Así descodificas. Como sabes que el primer carácter es una A. En el primer caso te queda:

\( A^{-1}(20,62,2)^t=(1,*,*) \)

 y de ahí podrás hallar el parámetro A.

 Sería bueno que te ayudases de algún programa para hacer los cálculos.

Saludos.

P.D. Intuyo que el mensaje está en catalán porque creo que empieza así:

Spoiler

Això sembla que ...

[cerrar]

¿Es posible?.

[zeikson]

Así es. Está en catalán.

Muchísimas gracias por la ayuda!!

Saludos.

[zeikson]

He seguido los pasos...pero me lio un poco.
Esto es lo que tengo:

El determinante en mod 139 sería el siguiente:

\( \begin{bmatrix} 1 & 5 & 8 \\ 7 & 15 & 74 \\ 8 & a & 1 \end{bmatrix} \) =15+56a+2960–(960+74a+35) = -18a +1980 =121a+34 (mod139)

Al no tener un determinante nulo, la matriz es valida.

Ahora para calcular la inversa se hace (1/determinante de A)*Adjunta de A


Para calcular la adjunta hacemos la traspuesta de los cofactores de A:
Primero Calculamos los cofactores

A11=\( \begin{bmatrix} 15 & 74 \\ a & 1 \end{bmatrix} \) A12=\( \begin{bmatrix} 7 & 4 \\ 8 & 1 \end{bmatrix} \) A=13=\( \begin{bmatrix} 7 & 15 \\ 8 & a \end{bmatrix} \)

A21=\( \begin{bmatrix} 5 & 8 \\ a & 1 \end{bmatrix} \)  A22=\( \begin{bmatrix} 1 & 8 \\ 8 & 1 \end{bmatrix} \)  A23=\( \begin{bmatrix} 1 & 5 \\ 8 & a \end{bmatrix} \)

A31=\( \begin{bmatrix} 5 & 8 \\ 15 & 74 \end{bmatrix} \)  A32=\( \begin{bmatrix} 1 & 8 \\ 7 & 15 \end{bmatrix} \)  A33=\( \begin{bmatrix} 1 & 5 \\ 7 & 15 \end{bmatrix} \)


A11= 15-74a
A12=-585
A13=7a -120
A21=5-8a
A22=-63
A23=a-40
A31=250
A32=18
A33=-20

A los cofactores impares se les cambia el signo:

A11= 15-74a
A12=-585=585
A13=7a -120
A21=5-8a= -5+8a
A22=-63
A23=a-40 = -a +40
A31=250
A32=18 =-18
A33=-20

Ahora hacemos el mod 139:

A11= 15-74a = 15+65a
A12=-585=585 = 29
A13=7a -120 = 7a +19
A21=5-8a= -5+8a =134+8a
A22=-63 = 76
A23=a-40 = -a +40 =138a +40
A31=250 =111
A32=18 =-18 = 121
A33=-20 =119

Al hacer la adjunta de la traspuesta quedaría:

\( \begin{bmatrix} 15+65a & 134+8a & 111 \\ 29 & 76 & 121 \\ 7a+19 & 138a+40 & 119\end{bmatrix} \)

Y la inversa sería:

121a+34 * \( \begin{bmatrix} 15+65a & 134+8a & 111 \\ 29 & 76 & 121 \\ 7a+19 & 138a+40 & 119\end{bmatrix} \)

Y una vez aquí no se como seguir con tanta matriz...

[Luis Fuentes]

Hola

 Las cuentas no las voy a revisar porque me da una pereza enoooorme. Me sorprende que tengas que hacer todo "a mano". Por que sin ayuda de un ordenador, descifrar el mensaje multiplicando cada 3 cifras, por la matriz que halles y pasar a módulo 139, todo hecho con lápiz y papel, es una ardua tarea.

 Un par de comentarios.

Al no tener un determinante nulo, la matriz es valida.

 El determinante te da \( 121a+34 \). Que sea nulo o no depende de si \( 121a+34\equiv 0 \). Entonces para algún valor de \( a \) si será nulo y la matriz no será válida. En concreto despejando:

\( a\equiv (-34)\cdot 121^{-1} \)

 Donde recuerda que el inverso has de hallarlo módulo \( 139 \). Entonces fuera de ese valor, te vale cualquier \( a \).

 En cuanto a la inversa, suponiendo que estén bien hechas la cuentas de la adjunta traspuesta, ojo, sería:

\( (121a+34)^{-1}\cdot \begin{bmatrix} 15+65a & 134+8a & 111 \\ 29 & 76 & 121 \\ 7a+19 & 138a+40 & 119\end{bmatrix} \)

 Ya que tienes que dividir por el determinante; no multiplicar. Ahora bien de momento déjalo así planteado y no dividas:

 Para hallar a sabes que:

\( (121a+34)^{-1}\cdot \begin{bmatrix} 15+65a & 134+8a & 111 \\ 29 & 76 & 121 \\ 7a+19 & 138a+40 & 119\end{bmatrix}\left[{\begin{array}{ccc}{20}\\{62}\\{2}\end{array}\right]=\left[{\begin{array}{ccc}{1}\\{*}\\{*}\end{array}\right] \)

 Luego pasando \( (121a+34) \) multiplicando al otro lado, te queda:

\( \begin{bmatrix} 15+65a & 134+8a & 111 \\ 29 & 76 & 121 \\ 7a+19 & 138a+40 & 119\end{bmatrix}\left[{\begin{array}{ccc}{20}\\{62}\\{2}\end{array}\right]=\left[{\begin{array}{ccc}{121a+34}\\{*}\\{*}\end{array}\right] \)

 De ahí podrás hallar \( a \) y trabajar con un valor concreto de éste.

 Si tienes que hacer todo a mano... paciencia.

Saludos.

[zeikson]

Hola de nuevo.

Sigo con este problema...

Multiplico fila por columna:

20(15+65a)+62(134+8a)+222=300+1300a+8308+4969+222=1796a+8830\( \equiv{128a+73(mod 139)} \)

Entonces sería:

128a+73=121a+34
7a+39\( \equiv{0 (mod 139)} \)
7a\( \equiv{-39} \)
a\( \equiv{\displaystyle\frac{100}{7} (mod 139)} \)

No deberia ser 'a' un número natural?
Estoy bastante perdido.

Saludos.

[Luis Fuentes]

Hola

 Ten cuidado. En \( Z_{139} \) dividir por \( 7 \), corresponde a multiplicar por el inverso de \( 7 \). Éste es un número entero \( x \) verificando que:

\( 7x\equiv_{139} 1 \) es decir \( 7x-139k=1 \)

 Para hallarlo puedes usar el algoritmo de Euclides:

\( 139=19*7+6 \)
\(    7=6*1+1 \)
 
 Y de ahí:

\( 1=7-(139-19*7)=20*7-139 \)

 Por tanto:

 \( 7^{-1}\equiv_{139}20 \)

 De manera que tu ecuación módulo 139:

 \( 7a+39\equiv 0 \)

 se resuelve:

 \( 7a\equiv -39\equiv 100 \)

 \( a\equiv 100\cdot 7^{-1}\equiv 100\cdot 20\equiv 2000 \equiv 54 \)

Saludos.