---

I forbindelse med RSA-kryptering skal man finde et tal som er primisk i
forhold til et andet. Skal man finde et tal der ikke går op i 10, og som
selv er et primtal,kan man vælge eksempelvis 7. Det er nemt nok for så små
tal, men hvad gør man egentlig når man har fat i de enorme tal, der anvendes
i mere sikker kryptering?

hvis jeg har et tal med flere hundrede bit størelse, hvordan finder jeg så
et primtal som ikke går op i dette store tal? Man kan naturligvis bare søge
efter primtal i intervallet ]tal/2;tal[ , men er det "sådan man gør"?

---

Jakob Nielsen wrote:
> I forbindelse med RSA-kryptering skal man finde et tal som er primisk i
> forhold til et andet. Skal man finde et tal der ikke går op i 10, og som
> selv er et primtal,kan man vælge eksempelvis 7. Det er nemt nok for så små
> tal, men hvad gør man egentlig når man har fat i de enorme tal, der anvendes
> i mere sikker kryptering?

> hvis jeg har et tal med flere hundrede bit størelse, hvordan finder jeg så
> et primtal som ikke går op i dette store tal? Man kan naturligvis bare søge
> efter primtal i intervallet ]tal/2;tal[ , men er det "sådan man gør"?

Hvis man har en metode til at "finde et tilfældigt primtal med 100 cifre" vil
man bare bruge den to gange for at finde to primtal til at konstruere
nøglerne udfra. Viser det sig, at man er så uheldig at få det samme primtal
to gange, så forsøger man bare igen. Sandsynligheden for, at det samme
primtal dukker op to gange i træk, er dog meget lille.

--
Jens Axel Søgaard

---

On Fri, 07 May 2004 18:08:09 +0200, Jakob Nielsen wrote:

> I forbindelse med RSA-kryptering skal man finde et tal som er primisk i
> forhold til et andet. Skal man finde et tal der ikke går op i 10, og som
> selv er et primtal,kan man vælge eksempelvis 7. Det er nemt nok for så små
> tal, men hvad gør man egentlig når man har fat i de enorme tal, der anvendes
> i mere sikker kryptering?
>
> hvis jeg har et tal med flere hundrede bit størelse, hvordan finder jeg så
> et primtal som ikke går op i dette store tal? Man kan naturligvis bare søge
> efter primtal i intervallet ]tal/2;tal[ , men er det "sådan man gør"?

Med kryptering er det ikke sådan at man skal primopløse et stort tal for
at bryde krypteringen ? Altså man skal finde et primtal der går op
i det store tal ?

Martin.

---

Jakob Nielsen wrote:
>
> hvis jeg har et tal med flere hundrede bit størelse, hvordan finder jeg så
> et primtal som ikke går op i dette store tal? Man kan naturligvis bare søge
> efter primtal i intervallet ]tal/2;tal[ , men er det "sådan man gør"?

Jeg aner ikke noget om den konkrete sammenhæng, men kan man ikke bare
prøve med de første få primtal, altså 2,3,5,7,11,13,17,...? Det skulle
da være meget sært hvis de alle gik op.

Det interval du angiver, kan ikke indholde divisorer; der er jo ikke
nogen hele tal (kvotienten) i intervallet ]1;2[.

--
Jeppe Stig Nielsen <URL:http://jeppesn.dk/>. «

"Je n'ai pas eu besoin de cette hypothèse (I had no need of that
hypothesis)" --- Laplace (1749-1827)

---

Jakob Nielsen wrote:

> I forbindelse med RSA-kryptering skal man finde et tal som er primisk i
> forhold til et andet. Skal man finde et tal der ikke går op i 10, og som
> selv er et primtal,kan man vælge eksempelvis 7. Det er nemt nok for så små
> tal, men hvad gør man egentlig når man har fat i de enorme tal, der anvendes
> i mere sikker kryptering?
>
> hvis jeg har et tal med flere hundrede bit størelse, hvordan finder jeg så
> et primtal som ikke går op i dette store tal? Man kan naturligvis bare søge
> efter primtal i intervallet ]tal/2;tal[ , men er det "sådan man gør"?

Jeg ved ikke hvilken del af nøglegenereringen du hentyder til.
Man finder to primtal p og q. Derefter skal man vælge d og e således at
de = 1 (mod (p-1)(q-1)).

Det er ikke ret svært at finde passende d og e. Man kan endda stort set
selv vælge den ene. Ofte vælger man e=3 eller e=65537 (for at gøre den
offentlige nøgle effektiv at regne på).
Læg dog mærke til at det kun kan lade sig gøre hvis den valgte e er
indbyrdes primisk med p-1 og q-1.
Dette er ikke noget problem i praksis: Man vælger blot e først, og
finder så p og q så p-1 og q-1 er primiske med e.

Uanset hvordan du vender og drejer det, så er der *mange* tal der er
indbyrdes primisk med både p-1 og q-1 - Jeg vil skyde på at det er i
størrelsesordenen "halvdelen af alle ulige tal" (plus/minus).

Mvh. Bjarke

---

> Jeg ved ikke hvilken del af nøglegenereringen du hentyder til.
> Man finder to primtal p og q. Derefter skal man vælge d og e således at
> de = 1 (mod (p-1)(q-1)).
>
> Det er ikke ret svært at finde passende d og e. Man kan endda stort set
> selv vælge den ene. Ofte vælger man e=3 eller e=65537 (for at gøre den
> offentlige nøgle effektiv at regne på).

Den del jeg tænker på er formuleret i en bog som
"choose an integer E which is prime relative to X"
X er tidligere beregnet som X=(P-1)*(Q-1) hvor P og Q er to store primtal.

Lad os sige at jeg vælger P som 101 og Q som 113. Små primtal, men kan vel
illustrere spørgsmålet.
Så er x=(101-1)*(113-1)=11200

Så skal et tal findes, som ikke går op i 11200. Du taler her om at vælge et
tal d*e, som opfylder dette. Jeg kan ikke helt se hvordan det gavner noget
at sige at e er 3. d skal stadig findes så d*e ikke går op i 11200. Som sagt
kan man søge tal som er over halvdelen af 11200, og mindre end 11200, men er
det sådan du vil finde tallet?

> Uanset hvordan du vender og drejer det, så er der *mange* tal der er
> indbyrdes primisk med både p-1 og q-1 - Jeg vil skyde på at det er i
> størrelsesordenen "halvdelen af alle ulige tal" (plus/minus).

Du vil bare vælge tilfældige tal og se om de går op? Der er ingen anden
metode, siden der er vilkåligt mange løsninger?

---

Jakob Nielsen wrote:
>
> Den del jeg tænker på er formuleret i en bog som
> "choose an integer E which is prime relative to X"
> X er tidligere beregnet som X=(P-1)*(Q-1) hvor P og Q er to store primtal.
>
> Lad os sige at jeg vælger P som 101 og Q som 113. Små primtal, men kan vel
> illustrere spørgsmålet.
> Så er x=(101-1)*(113-1)=11200
>
> Så skal et tal findes, som ikke går op i 11200.

Prøv med primtallene 2, 3, 5, 7, 11, ...

I dette eksempel viser det sig at 3 ikke går op.

Man vil altid meget hurtigt finde et primtal som ikke går op. Det aller-
værste tilfælde er hvis X tilfældigvis er på formen X = 2·3·5·...·p_n ,
altså et »primultets-tal«. Men selv i det tilfælde vil man ret hurtigt
komme til p_{n+1} som ikke går op.

--
Jeppe Stig Nielsen <URL:http://jeppesn.dk/>. «

"Je n'ai pas eu besoin de cette hypothèse (I had no need of that
hypothesis)" --- Laplace (1749-1827)

---

Jakob Nielsen wrote:

> Den del jeg tænker på er formuleret i en bog som
> "choose an integer E which is prime relative to X"
> X er tidligere beregnet som X=(P-1)*(Q-1) hvor P og Q er to store primtal.
>
> Lad os sige at jeg vælger P som 101 og Q som 113. Små primtal, men kan vel
> illustrere spørgsmålet.
> Så er x=(101-1)*(113-1)=11200
>
> Så skal et tal findes, som ikke går op i 11200. Du taler her om at vælge et
> tal d*e, som opfylder dette.

Nej, vi skal finde d*e == 1 (mod X). (Dvs. d*e har rest 1 når man
dividerer med X)
Det kan kun lade sig gøre hvis e og X er indbyrdes primiske (og d og X
er indbyrdes primiske), for ellers ville (d*e % X) jo være divisibel med
deres fælles faktor.

Som Jeppe Stig Nielsen skriver, er det ikke svært at finde e: bare prøv
nogle primtal indtil der er gevinst - det er nok den hurtigste metode.
Allerede 3 dur.

Så mangler vi bare at finde d.
Men det er ren ligningsløsning:

d*3 = 1 (mod 11200)
Dvs. der findes et M så
3*d = 1 + 11200 * M
dvs 11202 M = 1 + 11200 * M (med d=3734M)
dvs M = 2

så d = (2*11200+1) / 3 = 7467.

Man kan udlede en algoritme for beregning af d ud fra X og e - mon ikke
det er den der bygger på Kinesisk Restsætning? I hvert fald minder det
om Euklids algoritme.

Søgetip: "Chinese Remainder Theorem"


> Jeg kan ikke helt se hvordan det gavner noget
> at sige at e er 3. d skal stadig findes så d*e ikke går op i 11200.

Nej, hvis det var det man skulle, kunne du bare vælge d=e=3.
Kravet er d*e == 1 (mod X) - se ovenfor.


Mvh. Bjarke

---

Bjarke Dahl Ebert wrote:

> d*3 = 1 (mod 11200)
> Dvs. der findes et M så
> 3*d = 1 + 11200 * M (*)
> dvs 11202 M = 1 + 11200 * M (med d=3734M)
> dvs M = 2

Ups, jeg fik vist lige en hjerneblødning her.
Men det gør ikke noget, for M=2 er udmærket i linien (*)

Mvh. Bjarke