kongruenzen und RSA

05.02.2007, 11:05

tingol

kongruenzen und RSA

hi, habe folgende art von aufgaben:

ich soll alle Lösungen aus
$\begin{eqnarray*} Z_{135}^* \end{eqnarray*}$

(aber wenn ich mich erinnere hat die verknüpfungstafel (n-1)^2 elemente

$\begin{eqnarray*} 48*x+260\equiv 11 (mod 135) \end{eqnarray*}$

habe das ganze wie folgt umgeformt:

$\begin{eqnarray*} x = (135y-249)/48 \end{eqnarray*}$

weiter weis ich leider nicht, hoffe es kann mir jemand helfen, habe zwar schon die sufu benutze, werde aber nich schlau daraus

Ich soll auch die RSA entschlüsselungsfunktion zu
$\begin{eqnarray*} E(m) = m^43 (mod 403) \end{eqnarray*}$

da bin ich aber tatal platt, das einzige was mir einfiele, wäre die Methode des fortgesetzen quadrierens, um die hohen potenzen in den griff zu bekommen, aber sonst...

danke

05.02.2007, 11:19

piloan

Auf diesen Beitrag antworten »

hi
also erstmal gilt
$\begin{eqnarray*} 48x+260 \equiv 11\pmod{135} \end{eqnarray*}$
$\begin{eqnarray*} 48x \equiv -249\pmod{135}=48x \equiv 21\pmod{135} \end{eqnarray*}$

nun musst du das Inverse von 48 in Z/135Z finden. Das schaffst du mit dem erweiterten euklidschen Algorithmus.
musst du mal bei wiki suchen smile

05.02.2007, 11:22

Auf diesen Beitrag antworten »

48 und 135 sind nicht teilerfremd, also gibt es kein Inverses!

Allerdings kann man zunächst die ganze Gleichung $\begin{eqnarray*} 48x\equiv -249 \mod 135 \end{eqnarray*}$ (inklusive Modul!) durch den gemeinsamen Teiler 3 teilen

$\begin{eqnarray*} 16x\equiv -83\equiv 7\mod 45 \end{eqnarray*}$

und dann den EEA auf 16 und 45 loslassen.

05.02.2007, 12:20

tingol

Auf diesen Beitrag antworten »

Sorry ich habe grade meine unterlagen durchgesehen, aber ich finde nichts von einem Modul...

Beim EEA bekomme ich 1 raus,
$\begin{eqnarray*} 48*1+249(mod 135) = 48 * 1 -21 mod 135 = 27 \end{eqnarray*}$

also alle ergebnisse der Verknüpfungstafel, die einen rest von 27 haben?
x*y mod 135 = 27

wie bekomme ich die den blos alle zusammen

stimmt das so?

weibei wo kommen die 21 / 7 her? Modul?

05.02.2007, 12:30

piloan

Auf diesen Beitrag antworten »

hi
mit dem EEA bestimmst du 2 zahlen a,b ,sd

$\begin{eqnarray*} 16a+45b=1 \end{eqnarray*}$ welche zahlen a,b hast du jetzt dafuer rausbekommen ?...

05.02.2007, 12:37

tingol

Auf diesen Beitrag antworten »

$\begin{eqnarray*} ggT(16;45) = 45a + 16b = 1 \end{eqnarray*}$
$\begin{eqnarray*} a= 5 \end{eqnarray*}$
$\begin{eqnarray*} b = -14 \end{eqnarray*}$

05.02.2007, 12:47

piloan

Auf diesen Beitrag antworten »

ja dann hast du es doch

$\begin{eqnarray*} (-14)16x\equiv 1x\equiv-14*7 =-98 \equiv 37\pmod{45} \end{eqnarray*}$

05.02.2007, 13:02

tingol

Auf diesen Beitrag antworten »

leider nicht da ich nicht ganz verstehe woher die 7 kommt oder die 37

05.02.2007, 13:08

piloan

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent

$\begin{eqnarray*} 16x\equiv -83\equiv 7\mod 45 \end{eqnarray*}$

und dann den EEA auf 16 und 45 loslassen.

daher weisst du , das $\begin{eqnarray*} 16x\equiv 7\mod 45 \end{eqnarray*}$ ist.

nun multipliziert du beide seiten mit deinem inversen -14
daraus folgt $\begin{eqnarray*} 16(-14)x\equiv -14*7\mod 45 \end{eqnarray*}$ und
$\begin{eqnarray*} 16(-14)\equiv 1 mod 45 \end{eqnarray*}$ (da -14 das inverse ist )

und daraus folgt
$\begin{eqnarray*} 16(-14)x\equiv1x\equiv -14*7\mod 45 \end{eqnarray*}$ und nun musst du nur noch -14*7 ausrechnen zu mod45

05.02.2007, 13:16

tingol

Auf diesen Beitrag antworten »

Zitat:

Original von piloan
[quote]Original von Arthur Dent

$\begin{eqnarray*} 16x\equiv -83\equiv 7\mod 45 \end{eqnarray*}$

und dann den EEA auf 16 und 45 loslassen.

ja aber wo kommt die 7 her? das verstehe ich einfach nicht

05.02.2007, 13:21

piloan

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent

Allerdings kann man zunächst die ganze Gleichung $\begin{eqnarray*} 48x\equiv -249 \mod 135 \end{eqnarray*}$ (inklusive Modul!) durch den gemeinsamen Teiler 3 teilen

einfach nur doch 3 geteilt

05.02.2007, 14:45

tingol

Auf diesen Beitrag antworten »

$\begin{eqnarray*} 48/3=16 \end{eqnarray*}$
$\begin{eqnarray*} -249/3 =-83 \end{eqnarray*}$
$\begin{eqnarray*} 135/3=45 \end{eqnarray*}$

ja ich weis ich nerve wahrscheinlich, aber ich checks einfach nicht

$\begin{eqnarray*} 16x \equiv -83\equiv 7 (mod 45) \end{eqnarray*}$

woher kommt es auf einmal, vorher waren drei zahlen, jetzt sinds vier, ich steh voll auf dem schlauch
$\begin{eqnarray*} \equiv 7 \end{eqnarray*}$

05.02.2007, 15:11

Auf diesen Beitrag antworten »

Du kannst auch die -83 stehen lassen, aber "kleine" Zahlen sind nun mal angenehmer:

$\begin{eqnarray*} -83\equiv -83+2\cdot 45 = -83+90 = 7 \mod 45 \end{eqnarray*}$

Ganz normale, elementare Modulrechnung - das machst du doch nicht zum ersten Mal???

Neue Frage »

Antworten »

kongruenzen und RSA

Verwandte Themen