Modulo rechnen mit Intervall

28.06.2020, 14:16	Marisers	Auf diesen Beitrag antworten »
Modulo rechnen mit Intervall Hallo zusammen, ich gucke mir gerade ein Thema aus der Kryptographie an. Dabei soll eine Nachricht $\begin{eqnarray} m \end{eqnarray}$ multipliziert werden. Gerechnet wird dabei immer $\begin{eqnarray} \bmod n \end{eqnarray}$ (n ist das Produkt zweier Primzahlen). Abhängig davon, in welchem Intervall m liegt, kann man dann scheinbar das Ergebnis berechnen. Die "triviale" Tabelle wurde dabei wie folgt aufgestellt: [attach]51596[/attach] Die erste Zeile kann ich mir bei kurzem Nachdenken noch erklären. Wenn $\begin{eqnarray} m >= 0 \end{eqnarray}$ und $\begin{eqnarray} m < \frac{n}{4} \end{eqnarray}$ , dann ist $\begin{eqnarray} 4m < n \end{eqnarray}$ und somit $\begin{eqnarray} 4m \bmod n = 4m \end{eqnarray}$ . Aber ich bin mir nicht sicher, wie man den Rest mathematisch berechnen kann, da m ja kein fester Wert ist, sondern in einem Intervall liegen kann. Kann mir da jemand einen Tipp geben, wie man auf die "Lösung" kommt? LG
28.06.2020, 14:44	Helferlein	Auf diesen Beitrag antworten »
Wemn es Dir nur um die modulo-Rechnung geht: $\begin{eqnarray} \frac n4 \leq m \leq \frac n2 \Rightarrow 0=4 \cdot \frac n4-n \leq 4m-n \leq 4 \cdot \frac n2-n=n \end{eqnarray}$
28.06.2020, 16:20	Marisers	Auf diesen Beitrag antworten »
Danke, das macht Sinn. Für die 3. Zeile sollte es dann ja sein: $\begin{eqnarray} <br /> \frac{n}{2} \leq m \leq \frac{3n}{4} \Rightarrow 0 = 4 \cdot \frac{n}{2} -2n \leq 4m -2n \leq 4 \cdot \frac{3n}{4} -2n = n \end{eqnarray}$ Auf diese Weise kann ich ja praktisch die vorgegeben Lösung nachprüfen. Gibt es eine Möglichkeit vom Intervall ausgehend: $\begin{eqnarray} \left[\frac{n}{4}, \frac{n}{2}\right] \end{eqnarray}$ darauf zu schließen, dass $\begin{eqnarray} 4 \cdot m \bmod n = 4m - n \end{eqnarray}$ ist? Also prakitsch, ohne dass einem die 4m-n vorher bekannt sind. Desweiteren tue ich mich mit den Grenzen der Intervalle noch etwas schwer. Beispiel: $\begin{eqnarray} \frac{n}{4} \cdot 4 \bmod n = 0 \rightarrow \text{Gerade} \end{eqnarray}$ , was ja eigentlich der Tabelle widersprechen würde, da ja für alle m aus dem Intervall gelten soll, dass 4m mod n ungerade ist. Kann es sein, dass diese Tabelle nur "richtig" ist, wenn die Intervallgrenzen exklusiv sind? n ist ja das Produkt zweier Primzahlen und $\begin{eqnarray} m \in \mathbb{Z} \end{eqnarray}$ . Damit sollte niemals $\begin{eqnarray} m=\frac{n}{4} \vee m=\frac{n}{2} \vee m=\frac{3n}{4} \end{eqnarray}$ ja nie möglich sein und somit im Falle der zweiten Zeile etwa $\begin{eqnarray} m\in \left]\frac{n}{4}, \frac{n}{2}\right[ \end{eqnarray}$ gelten? Was mich dann aber verwirrt, ist in der letzten Zeile, dass $\begin{eqnarray} n-1 \text{ anstatt } n \end{eqnarray}$ steht. Wenn man die Spalte der Parität mit einbezieht, kann es sein, dass die Intervalle dann so definiert sein müssten, damit alle Aussagen der Tabelle stimmen? $\begin{eqnarray} \left[0, \frac{n}{2}\right[ \end{eqnarray}$ $\begin{eqnarray} \left]\frac{n}{4}, \frac{n}{2}\right[ \end{eqnarray}$ $\begin{eqnarray} \left[\frac{n}{2}, \frac{3n}{4}\right[ \end{eqnarray}$ $\begin{eqnarray} \left]\frac{3n}{4}, n-1 \right] \end{eqnarray}$ Hoffe ich hab jetzt nur mich selbst und nicht alle anderen auch komplett verwirrt.
28.06.2020, 16:53	Helferlein	Auf diesen Beitrag antworten »
Zum ersten: Du hast Intervalle der Länge $\begin{eqnarray} \frac n4 \end{eqnarray}$ und willst diese auf die Länge n bringen. Was ist das naheliegenste? Um dann die richtigen Reste zu bekommen, muss anschließend das Intervall verschoben werden. Zu den Grenzen: Wenn n das Produkt zweier Primzahlen ist, wird die Grenze in den wenigsten Fällen ausgeschöpft. Es spricht aber bis auf die Wohldefiniertheit nichts dagegen, die Grenzen entsprechend zu setzen. Zu dem n-1: Ist vielleicht m<n gefordert? Du hast bisher nicht viel über das n erzählt.
28.06.2020, 18:12	Marisers	Auf diesen Beitrag antworten »
Danke. Ich setze also praktisch die untere und obere Grenze ein und schaue wie oft ich "n" abziehen muss um mit der unteren Grenze wieder auf 0 und mit der oberen Grenze auf n zu kommen. Was mich an dieser Tabelle noch stört: Für m=n/4 und m=n/2 sind ist die Parität in der Tabelle sowohl Gerade als auch Ungerade, was ja nicht sein kann. Um mal etwas mehr zu dem Hintergrund zu sagen: Der Kontext ist die RSA-Verschlüsselung. Ein Text m wird verschlüsselt mit: $\begin{eqnarray} E(m) = m^{e} \bmod n = c \end{eqnarray}$ Der Exponent e und der Modulus n sind öffentlich. Der Modulus n ist immer das Produkt zweier Primzahlen. m < n gilt auch. Der Empfänger entschlüsselt die Nachricht mit seinem privaten Exponenten d. $\begin{eqnarray} D(c) = c^{d} \bmod n = m^{e^{d}} \bmod n = m \end{eqnarray}$ Ich beschäftige mich aktuell mit einem Angriff auf dieses System. Angenommen ich habe einen verschlüsselten Text "c" abgefangen und habe ein Orakel, dass mir die Parität des zugehörigen Klartextes verrät: O(c) = gerade oder ungerade Es wird also praktisch das letzte Bit des Textes geleakt. Dann kann man die Homomorphieeigenschaften nutzen um den gesamten Text zu entschlüsseln. In dem Rahmen ist die ursprüngliche Tabelle entstanden. Die Idee ist also den Klartext im ersten Schritt mit 2 zu multiplizieren. $\begin{eqnarray} c' = c2^{e} \bmod n = m^{e}2^{e} \bmod n = (m\cdot 2)^{e} \bmod n = E(m \cdot 2) \end{eqnarray}$ . Wenn O(c') = "gerade", dann kann man daraus schließen, dass $\begin{eqnarray} 2m < n \end{eqnarray}$ , und somit $\begin{eqnarray} m < \frac{n}{2} \end{eqnarray}$ . Im 2. Schritt würde man dann den Klartext indirekt mit 4 multiplizieren, im 3. Schritt mit 8, im i-ten Schritt mit 2^i und hätte dann nach log(n) Schritten den gesamten Klartext entschlüsselt. Wenn ich jetzt nochmal auf die Tabelle schaue, dann finde ich die Grenzen nicht intuitiv, weil sie ja teilweise mehrfach auftauchen und dann auf unterschiedliche Paritäten schließen. Angenommen $\begin{eqnarray} m=\frac{n}{2} \end{eqnarray}$ . Dann gilt laut der 2. Zeile: $\begin{eqnarray} \frac{4n}{2} \bmod n = \frac{4n}{2} - n = n \end{eqnarray}$ , was ja nicht korrekt ist, da $\begin{eqnarray} \frac{4n}{2} \bmod n = 0 \end{eqnarray}$ . Aber ich denke, ich muss mir einfach klar machen, dass m unter Berücksichtigung von n (Produkt zweier Primzahlen) nie n/4 etc. sein kann?
28.06.2020, 20:28	Helferlein	Auf diesen Beitrag antworten »
Zur Verschlüsselung nimmt man zwei möglichst große Primzahlen, also ist n ungerade und somit $\begin{eqnarray} m=\frac n2 \end{eqnarray}$ nicht möglich.
Anzeige

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »