Protokół Diffiego-Hellmana. Szyfrowanie RSA. Podpis cyfrowy - Historia wersji

HenrykDabrowski o 18:38, 20 sty 2026

2026-01-20T18:38:13Z

HenrykDabrowski o 17:20, 16 gru 2025

2025-12-16T17:20:23Z

← poprzednia wersja		Wersja z 19:20, 16 gru 2025
Linia 288:		Linia 288:
	:# Wybierzmy liczbę <math>e</math> tak, aby spełniała warunki <math>\gcd (e, \Phi) = 1</math> i <math>2 < e < \Phi</math>		:# Wybierzmy liczbę <math>e</math> tak, aby spełniała warunki <math>\gcd (e, \Phi) = 1</math> i <math>2 < e < \Phi</math>
	:#* zaleca się, aby <math>e \geqslant 65537</math>		:#* zaleca się, aby <math>e \geqslant 65537</math>
	:# Z lematu Bézouta (zobacz C75) istnieją takie liczby całkowite <math>d</math> i <math>k</math>, że <math>d e + k \Phi = 1</math>. Liczbę <math>d</math> wyliczamy ze wzoru <math>d = d_0 + \Phi t</math>, gdzie <math>d_0</math> (oraz <math>k_0</math>) otrzymujemy, wykorzystując w PARI/GP funkcję <code>gcdext(e, Φ)</code> (zobacz ~~C80~~)		:# Z lematu Bézouta (zobacz C75) istnieją takie liczby całkowite <math>d</math> i <math>k</math>, że <math>d e + k \Phi = 1</math>. Liczbę <math>d</math> wyliczamy ze wzoru <math>d = d_0 + \Phi t</math>, gdzie <math>d_0</math> (oraz <math>k_0</math>) otrzymujemy, wykorzystując w PARI/GP funkcję <code>gcdext(e, Φ)</code> (zobacz C83)
	:#* <math>d</math> wybieramy tak, aby była liczbą dodatnią, wtedy <math>k</math> musi być liczbą ujemną		:#* <math>d</math> wybieramy tak, aby była liczbą dodatnią, wtedy <math>k</math> musi być liczbą ujemną
	:#* <math>d</math> nie może być zbyt małą liczbą; pokazano<ref name="BonehDurfee1"/>, że powinno być <math>d > m^{0.292}</math>		:#* <math>d</math> nie może być zbyt małą liczbą; pokazano<ref name="BonehDurfee1"/>, że powinno być <math>d > m^{0.292}</math>

HenrykDabrowski o 12:07, 18 lis 2025

2025-11-18T12:07:08Z

← poprzednia wersja		Wersja z 14:07, 18 lis 2025
Linia 288:		Linia 288:
	:# Wybierzmy liczbę <math>e</math> tak, aby spełniała warunki <math>\gcd (e, \Phi) = 1</math> i <math>2 < e < \Phi</math>		:# Wybierzmy liczbę <math>e</math> tak, aby spełniała warunki <math>\gcd (e, \Phi) = 1</math> i <math>2 < e < \Phi</math>
	:#* zaleca się, aby <math>e \geqslant 65537</math>		:#* zaleca się, aby <math>e \geqslant 65537</math>
	:# Z lematu Bézouta (zobacz ~~C74~~) istnieją takie liczby całkowite <math>d</math> i <math>k</math>, że <math>d e + k \Phi = 1</math>. Liczbę <math>d</math> wyliczamy ze wzoru <math>d = d_0 + \Phi t</math>, gdzie <math>d_0</math> (oraz <math>k_0</math>) otrzymujemy, wykorzystując w PARI/GP funkcję <code>gcdext(e, Φ)</code> (zobacz ~~C79~~)		:# Z lematu Bézouta (zobacz C75) istnieją takie liczby całkowite <math>d</math> i <math>k</math>, że <math>d e + k \Phi = 1</math>. Liczbę <math>d</math> wyliczamy ze wzoru <math>d = d_0 + \Phi t</math>, gdzie <math>d_0</math> (oraz <math>k_0</math>) otrzymujemy, wykorzystując w PARI/GP funkcję <code>gcdext(e, Φ)</code> (zobacz C80)
	:#* <math>d</math> wybieramy tak, aby była liczbą dodatnią, wtedy <math>k</math> musi być liczbą ujemną		:#* <math>d</math> wybieramy tak, aby była liczbą dodatnią, wtedy <math>k</math> musi być liczbą ujemną
	:#* <math>d</math> nie może być zbyt małą liczbą; pokazano<ref name="BonehDurfee1"/>, że powinno być <math>d > m^{0.292}</math>		:#* <math>d</math> nie może być zbyt małą liczbą; pokazano<ref name="BonehDurfee1"/>, że powinno być <math>d > m^{0.292}</math>

HenrykDabrowski o 11:50, 31 maj 2024

2024-05-31T11:50:02Z

← poprzednia wersja		Wersja z 13:50, 31 maj 2024
Linia 288:		Linia 288:
	:# Wybierzmy liczbę <math>e</math> tak, aby spełniała warunki <math>\gcd (e, \Phi) = 1</math> i <math>2 < e < \Phi</math>		:# Wybierzmy liczbę <math>e</math> tak, aby spełniała warunki <math>\gcd (e, \Phi) = 1</math> i <math>2 < e < \Phi</math>
	:#* zaleca się, aby <math>e \geqslant 65537</math>		:#* zaleca się, aby <math>e \geqslant 65537</math>
	:# Z lematu Bézouta (zobacz ~~C73~~) istnieją takie liczby całkowite <math>d</math> i <math>k</math>, że <math>d e + k \Phi = 1</math>. Liczbę <math>d</math> wyliczamy ze wzoru <math>d = d_0 + \Phi t</math>, gdzie <math>d_0</math> (oraz <math>k_0</math>) otrzymujemy, wykorzystując w PARI/GP funkcję <code>gcdext(e, Φ)</code> (zobacz ~~C78~~)		:# Z lematu Bézouta (zobacz C74) istnieją takie liczby całkowite <math>d</math> i <math>k</math>, że <math>d e + k \Phi = 1</math>. Liczbę <math>d</math> wyliczamy ze wzoru <math>d = d_0 + \Phi t</math>, gdzie <math>d_0</math> (oraz <math>k_0</math>) otrzymujemy, wykorzystując w PARI/GP funkcję <code>gcdext(e, Φ)</code> (zobacz C79)
	:#* <math>d</math> wybieramy tak, aby była liczbą dodatnią, wtedy <math>k</math> musi być liczbą ujemną		:#* <math>d</math> wybieramy tak, aby była liczbą dodatnią, wtedy <math>k</math> musi być liczbą ujemną
	:#* <math>d</math> nie może być zbyt małą liczbą; pokazano<ref name="BonehDurfee1"/>, że powinno być <math>d > m^{0.292}</math>		:#* <math>d</math> nie może być zbyt małą liczbą; pokazano<ref name="BonehDurfee1"/>, że powinno być <math>d > m^{0.292}</math>

HenrykDabrowski o 16:45, 17 mar 2024

2024-03-17T16:45:51Z

← poprzednia wersja		Wersja z 18:45, 17 mar 2024
Linia 95:		Linia 95:
	Udowodnimy, że jeżeli <math>g</math> jest generatorem modulo <math>p</math>, to <math>g</math> jest liczbą niekwadratową modulo <math>p</math>.		Udowodnimy, że jeżeli <math>g</math> jest generatorem modulo <math>p</math>, to <math>g</math> jest liczbą niekwadratową modulo <math>p</math>.

	Przypuśćmy, że <math>g</math> jest liczbą kwadratową modulo <math>p</math>, zatem (zobacz ~~J30~~)		Przypuśćmy, że <math>g</math> jest liczbą kwadratową modulo <math>p</math>, zatem (zobacz J31)

	::<math>g^{(p - 1) / 2} \equiv 1 \!\! \pmod{p}</math>		::<math>g^{(p - 1) / 2} \equiv 1 \!\! \pmod{p}</math>
Linia 141:		Linia 141:
	::<math>\varphi (p - 1) = \varphi (2 q) = q - 1 = {\small\frac{p - 1}{2}} - 1</math>		::<math>\varphi (p - 1) = \varphi (2 q) = q - 1 = {\small\frac{p - 1}{2}} - 1</math>

	Ponieważ istnieje <math>{\small\frac{p - 1}{2}}</math> liczb niekwadratowych modulo <math>p</math> (zobacz ~~J29~~), to liczb niekwadratowych modulo <math>p</math>, różnych od <math>- 1</math>, jest <math>{\small\frac{p - 1}{2}} - 1</math>, czyli tyle samo, co generatorów modulo <math>p</math>, a żadna z pozostałych liczb (kwadratowych modulo <math>p</math>) nie może być generatorem modulo <math>p</math>. Co kończy dowód.<br/>		Ponieważ istnieje <math>{\small\frac{p - 1}{2}}</math> liczb niekwadratowych modulo <math>p</math> (zobacz J30), to liczb niekwadratowych modulo <math>p</math>, różnych od <math>- 1</math>, jest <math>{\small\frac{p - 1}{2}} - 1</math>, czyli tyle samo, co generatorów modulo <math>p</math>, a żadna z pozostałych liczb (kwadratowych modulo <math>p</math>) nie może być generatorem modulo <math>p</math>. Co kończy dowód.<br/>
	□		□
	{{\Spoiler}}		{{\Spoiler}}
Linia 154:		Linia 154:
	::<math>\left( {\small\frac{- 4}{p}} \right)_{\small{\!\! J}} = \left( {\small\frac{- 1}{p}} \right)_{\small{\!\! J}} \cdot \left( {\small\frac{2}{p}} \right)_{\small{\!\! J}}^{\! 2} = (- 1) \cdot (\pm 1)^2 = - 1</math>		::<math>\left( {\small\frac{- 4}{p}} \right)_{\small{\!\! J}} = \left( {\small\frac{- 1}{p}} \right)_{\small{\!\! J}} \cdot \left( {\small\frac{2}{p}} \right)_{\small{\!\! J}}^{\! 2} = (- 1) \cdot (\pm 1)^2 = - 1</math>

	Zobacz twierdzenie ~~J41~~ p.6.		Zobacz twierdzenie J42 p.6.


Linia 169:		Linia 169:
	::<math>\left( {\small\frac{- 3}{p}} \right)_{\small{\!\! J}} = \left( {\small\frac{- 1}{p}} \right)_{\small{\!\! J}} \cdot \left( {\small\frac{3}{p}} \right)_{\small{\!\! J}} = (- 1) \cdot (+ 1) = - 1</math>		::<math>\left( {\small\frac{- 3}{p}} \right)_{\small{\!\! J}} = \left( {\small\frac{- 1}{p}} \right)_{\small{\!\! J}} \cdot \left( {\small\frac{3}{p}} \right)_{\small{\!\! J}} = (- 1) \cdot (+ 1) = - 1</math>

	Zobacz twierdzenie ~~J41~~ p.6 i zadanie ~~J46~~.		Zobacz twierdzenie J42 p.6 i zadanie J47.


Linia 237:		Linia 237:
	::<math>a^{(p - 1) k + 1} = a \cdot (a^{p - 1})^k \equiv a \!\! \pmod{p}</math>		::<math>a^{(p - 1) k + 1} = a \cdot (a^{p - 1})^k \equiv a \!\! \pmod{p}</math>

	gdzie skorzystaliśmy z twierdzenia Fermata (~~J21~~).<br/>		gdzie skorzystaliśmy z twierdzenia Fermata (J22).<br/>
	□		□
	{{\Spoiler}}		{{\Spoiler}}

HenrykDabrowski o 11:19, 17 lut 2024

2024-02-17T11:19:36Z

Podgląd zmian

HenrykDabrowski o 13:29, 30 gru 2023

2023-12-30T13:29:48Z

← poprzednia wersja		Wersja z 15:29, 30 gru 2023
Linia 95:		Linia 95:
	Udowodnimy, że jeżeli <math>g</math> jest generatorem modulo <math>p</math>, to <math>g</math> jest liczbą niekwadratową modulo <math>p</math>.		Udowodnimy, że jeżeli <math>g</math> jest generatorem modulo <math>p</math>, to <math>g</math> jest liczbą niekwadratową modulo <math>p</math>.

	Przypuśćmy, że <math>g</math> jest liczbą kwadratową modulo <math>p</math>, zatem (zobacz ~~J27~~)		Przypuśćmy, że <math>g</math> jest liczbą kwadratową modulo <math>p</math>, zatem (zobacz J30)

	::<math>g^{(p - 1) / 2} \equiv 1 \!\! \pmod{p}</math>		::<math>g^{(p - 1) / 2} \equiv 1 \!\! \pmod{p}</math>
Linia 141:		Linia 141:
	::<math>\varphi (p - 1) = \varphi (2 q) = q - 1 = {\small\frac{p - 1}{2}} - 1</math>		::<math>\varphi (p - 1) = \varphi (2 q) = q - 1 = {\small\frac{p - 1}{2}} - 1</math>

	Ponieważ istnieje <math>{\small\frac{p - 1}{2}}</math> liczb niekwadratowych modulo <math>p</math> (zobacz ~~J26~~), to liczb niekwadratowych modulo <math>p</math>, różnych od <math>- 1</math>, jest <math>{\small\frac{p - 1}{2}} - 1</math>, czyli tyle samo, co generatorów modulo <math>p</math>, a żadna z pozostałych liczb (kwadratowych modulo <math>p</math>) nie może być generatorem modulo <math>p</math>. Co kończy dowód.<br/>		Ponieważ istnieje <math>{\small\frac{p - 1}{2}}</math> liczb niekwadratowych modulo <math>p</math> (zobacz J29), to liczb niekwadratowych modulo <math>p</math>, różnych od <math>- 1</math>, jest <math>{\small\frac{p - 1}{2}} - 1</math>, czyli tyle samo, co generatorów modulo <math>p</math>, a żadna z pozostałych liczb (kwadratowych modulo <math>p</math>) nie może być generatorem modulo <math>p</math>. Co kończy dowód.<br/>
	□		□
	{{\Spoiler}}		{{\Spoiler}}
Linia 154:		Linia 154:
	::<math>\left( {\small\frac{- 4}{p}} \right)_{\small{\!\! J}} = \left( {\small\frac{- 1}{p}} \right)_{\small{\!\! J}} \cdot \left( {\small\frac{2}{p}} \right)_{\small{\!\! J}}^{\! 2} = (- 1) \cdot (\pm 1)^2 = - 1</math>		::<math>\left( {\small\frac{- 4}{p}} \right)_{\small{\!\! J}} = \left( {\small\frac{- 1}{p}} \right)_{\small{\!\! J}} \cdot \left( {\small\frac{2}{p}} \right)_{\small{\!\! J}}^{\! 2} = (- 1) \cdot (\pm 1)^2 = - 1</math>

	Zobacz twierdzenie ~~J38~~ p.6.		Zobacz twierdzenie J41 p.6.


Linia 169:		Linia 169:
	::<math>\left( {\small\frac{- 3}{p}} \right)_{\small{\!\! J}} = \left( {\small\frac{- 1}{p}} \right)_{\small{\!\! J}} \cdot \left( {\small\frac{3}{p}} \right)_{\small{\!\! J}} = (- 1) \cdot (+ 1) = - 1</math>		::<math>\left( {\small\frac{- 3}{p}} \right)_{\small{\!\! J}} = \left( {\small\frac{- 1}{p}} \right)_{\small{\!\! J}} \cdot \left( {\small\frac{3}{p}} \right)_{\small{\!\! J}} = (- 1) \cdot (+ 1) = - 1</math>

	Zobacz twierdzenie ~~J38~~ p.6 i zadanie ~~J43~~.		Zobacz twierdzenie J41 p.6 i zadanie J46.

HenrykDabrowski o 13:19, 30 gru 2023

2023-12-30T13:19:04Z

← poprzednia wersja		Wersja z 15:19, 30 gru 2023
Linia 95:		Linia 95:
	Udowodnimy, że jeżeli <math>g</math> jest generatorem modulo <math>p</math>, to <math>g</math> jest liczbą niekwadratową modulo <math>p</math>.		Udowodnimy, że jeżeli <math>g</math> jest generatorem modulo <math>p</math>, to <math>g</math> jest liczbą niekwadratową modulo <math>p</math>.

	Przypuśćmy, że <math>g</math> jest liczbą kwadratową modulo <math>p</math>, zatem (zobacz ~~J25~~)		Przypuśćmy, że <math>g</math> jest liczbą kwadratową modulo <math>p</math>, zatem (zobacz J27)

	::<math>g^{(p - 1) / 2} \equiv 1 \!\! \pmod{p}</math>		::<math>g^{(p - 1) / 2} \equiv 1 \!\! \pmod{p}</math>
Linia 141:		Linia 141:
	::<math>\varphi (p - 1) = \varphi (2 q) = q - 1 = {\small\frac{p - 1}{2}} - 1</math>		::<math>\varphi (p - 1) = \varphi (2 q) = q - 1 = {\small\frac{p - 1}{2}} - 1</math>

	Ponieważ istnieje <math>{\small\frac{p - 1}{2}}</math> liczb niekwadratowych modulo <math>p</math> (zobacz ~~J24~~), to liczb niekwadratowych modulo <math>p</math>, różnych od <math>- 1</math>, jest <math>{\small\frac{p - 1}{2}} - 1</math>, czyli tyle samo, co generatorów modulo <math>p</math>, a żadna z pozostałych liczb (kwadratowych modulo <math>p</math>) nie może być generatorem modulo <math>p</math>. Co kończy dowód.<br/>		Ponieważ istnieje <math>{\small\frac{p - 1}{2}}</math> liczb niekwadratowych modulo <math>p</math> (zobacz J26), to liczb niekwadratowych modulo <math>p</math>, różnych od <math>- 1</math>, jest <math>{\small\frac{p - 1}{2}} - 1</math>, czyli tyle samo, co generatorów modulo <math>p</math>, a żadna z pozostałych liczb (kwadratowych modulo <math>p</math>) nie może być generatorem modulo <math>p</math>. Co kończy dowód.<br/>
	□		□
	{{\Spoiler}}		{{\Spoiler}}
Linia 154:		Linia 154:
	::<math>\left( {\small\frac{- 4}{p}} \right)_{\small{\!\! J}} = \left( {\small\frac{- 1}{p}} \right)_{\small{\!\! J}} \cdot \left( {\small\frac{2}{p}} \right)_{\small{\!\! J}}^{\! 2} = (- 1) \cdot (\pm 1)^2 = - 1</math>		::<math>\left( {\small\frac{- 4}{p}} \right)_{\small{\!\! J}} = \left( {\small\frac{- 1}{p}} \right)_{\small{\!\! J}} \cdot \left( {\small\frac{2}{p}} \right)_{\small{\!\! J}}^{\! 2} = (- 1) \cdot (\pm 1)^2 = - 1</math>

	Zobacz twierdzenie ~~J36~~ p.6.		Zobacz twierdzenie J38 p.6.


Linia 169:		Linia 169:
	::<math>\left( {\small\frac{- 3}{p}} \right)_{\small{\!\! J}} = \left( {\small\frac{- 1}{p}} \right)_{\small{\!\! J}} \cdot \left( {\small\frac{3}{p}} \right)_{\small{\!\! J}} = (- 1) \cdot (+ 1) = - 1</math>		::<math>\left( {\small\frac{- 3}{p}} \right)_{\small{\!\! J}} = \left( {\small\frac{- 1}{p}} \right)_{\small{\!\! J}} \cdot \left( {\small\frac{3}{p}} \right)_{\small{\!\! J}} = (- 1) \cdot (+ 1) = - 1</math>

	Zobacz twierdzenie ~~J36~~ p.6 i zadanie ~~J41~~.		Zobacz twierdzenie J38 p.6 i zadanie J43.


Linia 237:		Linia 237:
	::<math>a^{(p - 1) k + 1} = a \cdot (a^{p - 1})^k \equiv a \!\! \pmod{p}</math>		::<math>a^{(p - 1) k + 1} = a \cdot (a^{p - 1})^k \equiv a \!\! \pmod{p}</math>

	gdzie skorzystaliśmy z twierdzenia Fermata (~~J19~~).<br/>		gdzie skorzystaliśmy z twierdzenia Fermata (J21).<br/>
	□		□
	{{\Spoiler}}		{{\Spoiler}}

HenrykDabrowski o 10:55, 4 gru 2023

2023-12-04T10:55:36Z

← poprzednia wersja		Wersja z 12:55, 4 gru 2023
Linia 344:		Linia 344:
	d = '''gcdext'''(e, Phi)[1];		d = '''gcdext'''(e, Phi)[1];
	);		);
	'''print'''("m = ", m);		'''return'''([m, e, d]);
	'''print'''("e = ", e);		}</span>
	'''print'''("d = ", d);
			<span style="font-size: 90%; color:black;">PrintRSAkeys(w) =
			{
			'''local'''(V);
			V = RSAkeys(w);
			'''print'''("m = ", V[1]);
			'''print'''("e = ", V[2]);
			'''print'''("d = ", V[3]);
	}</span>		}</span>
	~~<br/>~~
	{{\Spoiler}}		{{\Spoiler}}

HenrykDabrowski: Utworzono nową stronę "
22.11.2023
FORCETOC == Protokół Diffiego-Hellmana ==
2023-11-22T16:31:58Z

Utworzono nową stronę "<div style="text-align:right; font-size: 130%; font-style: italic; font-weight: bold;">22.11.2023</div> FORCETOC == Protokół Diffiego-Hellmana == <span style=…"
Podgląd zmian