19-amaliy mashg’ulot

20-amaliy mashg’ulot
Mavzu: Rabin ochiq kalitli shifrlash algoritmining dasturiy vositasini ishlab chiqish. Rabin shifrlash algoritmi dasturini loyihalash
Rabin kriptotizimi Maykl Rabin tomonidan ixtiro qilingan ochiq kalitli kriptotizimdir. U ikki tomon o'rtasida muloqot qilish va xabarni shifrlash uchun assimetrik kalit shifrlashdan foydalanadi.
Rabin kriptotizimining xavfsizligi faktorizatsiyaning qiyinligi bilan bog'liq. Boshqalardan ustunligi shundaki, u bankka qo'yadigan muammo butun sonlarni faktorizatsiya qilish kabi qiyin bo'lib chiqdi. Bundan tashqari, Rabin funktsiyasining har bir chiqishi to'rtta mumkin bo'lgan har qanday kirish orqali yaratilishi mumkin bo'lgan kamchilikka ega. agar har bir chiqish shifrlangan matn bo'lsa, to'rtta mumkin bo'lgan kirishdan qaysi biri haqiqiy ochiq matn ekanligini aniqlash uchun shifrni ochishda qo'shimcha murakkablik talab etiladi.
Rabin kriptotizimining bajarilish ketma-ketligi:
Kalitlarni generatsiyalash
Ikkita juda katta tub sonlarni, p va q hosil qilinadi
p ≠ q → p ≡ q ≡ 3 (mod 4)
Masalan:
p=139 va q=191
n qiymatini hisoblanadi
n = p.q
n ni ochiq kalit sifatida va p va q ni shaxsiy kalit sifatida olinadi.
Shifrlash.
1. ni hisoblab olamiz n=q·p=19·43=817
2. Matnni 10lik sanoq ti sitemasida ifodalaymiz:
.
M=79, 76, 84, 73.
2. formula yordamida shifrlash amalga oshiriladi:




shifrtekst hosil bo‘ldi.
Shifrni ochish.
Shifrni ochish jarayoniga ko‘proq vaqt sarflanadi.Shifrmatndagi har bir son alohida olinadi. ni ko‘rib chiqamiz.
1. m1 = C mod p=52211 mod 43=36
2. m =(p-C )mod p =(43-36) mod 43=7
3. m =C mod q=5225 mod 19=16
4. m =(q-C ) mod q=(19-16) mod 19=3
5. a va b larni hisoblash uchun larning teskarisini topamiz:
p modq=43-1mod 19= 517 mod 19=4
q modp=19-1 mod 43=1941 mod 43=34
6. a=p(p mod q)=43·4=172
b=q(q mod p)=19·34=646
7. M =(a·m +b·m ) mod n=(172·16+646·36) mod 817=681
8. M =(a·m +b·m ) mod n=(172·3+646·36) mod 817=79
9. M =(a·m +b·m ) mod n=(172·16+646·7) mod 817=738
10. M =(a·m +b·m ) mod n=(172·3+646·7) mod 817=136
Olingan M1, M2, M3, M4 lardan 127 dan kichiklarini o‘n oltilik sanoq tizimiga o‘tkazamiz: 7910=>4F16=>O harfi paydo bo‘ldi.
1-10 qadamlar larning har biri uchun alohida hisoblanadi.Shu orqali bizda ochiq matn hosil bo‘ladi.
Rabin kriptotizimining dasturini quyida algoritmi keltirilgan:
import java.math.BigInteger;
import java.nio.charset.Charset;
import java.security.SecureRandom;
import java.util.Random;
class Cryptography {
private static Random r = new SecureRandom();
private static BigInteger TWO = BigInteger.valueOf(2);
private static BigInteger THREE = BigInteger.valueOf(3);
private static BigInteger FOUR = BigInteger.valueOf(4);
public static BigInteger[] generateKey(int bitLength)
{
BigInteger p = blumPrime(bitLength / 2);
BigInteger q = blumPrime(bitLength / 2);
BigInteger N = p.multiply(q);
return new BigInteger[] { N, p, q };
}
public static BigInteger encrypt(BigInteger m,
BigInteger N)
{
return m.modPow(TWO, N);
}
public static BigInteger[] decrypt(BigInteger c,
BigInteger p,
BigInteger q)
{
BigInteger N = p.multiply(q);
BigInteger p1 = c.modPow(p
.add(BigInteger.ONE)
.divide(FOUR),
p);
BigInteger p2 = p.subtract(p1);
BigInteger q1 = c.modPow(q
.add(BigInteger.ONE)
.divide(FOUR),
q);
BigInteger q2 = q.subtract(q1);
BigInteger[] ext = Gcd(p, q);
BigInteger y_p = ext[1];
BigInteger y_q = ext[2];
BigInteger d1 = y_p.multiply(p)
.multiply(q1)
.add(y_q.multiply(q)
.multiply(p1))
.mod(N);
BigInteger d2 = y_p.multiply(p)
.multiply(q2)
.add(y_q.multiply(q)
.multiply(p1))
.mod(N);
BigInteger d3 = y_p.multiply(p)
.multiply(q1)
.add(y_q.multiply(q)
.multiply(p2))
.mod(N);
BigInteger d4 = y_p.multiply(p)
.multiply(q2)
.add(y_q.multiply(q)
.multiply(p2))
.mod(N);
return new BigInteger[] { d1, d2, d3, d4 };
}
public staticBigInteger[] Gcd(BigInteger a, BigInteger b)
{
BigInteger s = BigInteger.ZERO;
BigInteger old_s = BigInteger.ONE;
BigInteger t = BigInteger.ONE;
BigInteger old_t = BigInteger.ZERO;
BigInteger r = b;
BigInteger old_r = a;
while (!r.equals(BigInteger.ZERO)) {
BigInteger q = old_r.divide(r);
BigInteger tr = r;
r = old_r.subtract(q.multiply(r));
old_r = tr;
BigInteger ts = s;
s = old_s.subtract(q.multiply(s));
old_s = ts;
BigInteger tt = t;
t = old_t.subtract(q.multiply(t));
old_t = tt;
}
return new BigInteger[] { old_r, old_s, old_t };
}
public static BigInteger blumPrime(int bitLength)
{
BigInteger p;
do {
p = BigInteger.probablePrime(bitLength, r);
} while (!p.mod(FOUR).equals(THREE));
return p; }}
public class RabinCryptosystem {
public static void main(String[] args)
{
BigInteger[] key = Cryptography.generateKey(512);
BigInteger n = key[0];
BigInteger p = key[1];
BigInteger q = key[2];
String finalMessage = null;
int i = 1;
String s = "Hello";
System.out.println("Message sent by sender : " + s);
BigInteger m
= new BigInteger(
s.getBytes(
Charset.forName("ascii")));
BigInteger c = Cryptography.encrypt(m, n);
System.out.println("Encrypted Message : " + c);
BigInteger[] m2 = Cryptography.decrypt(c, p, q);
for (BigInteger b : m2) {
String dec = new String(
b.toByteArray(),
Charset.forName("ascii"));
if (dec.equals(s)) {
finalMessage = dec; }
i++;
}
System.out.println(
"Message received by Receiver : "
+ finalMessage);
}

Topshiriq:

Ixtiyoriy dasturlash tilida Rabin shifrlash algoritmini dasturini tuzing va ishga tushiring.
Rabin shifrlash algoritming Class sinfini yaraning yarating.
O’z ismingizni va familiyangizni Rabin shifrlash dasturida shifrlang va deshifrlang.
Nazorat savollari:
Assimmetrik kriprografik algoritmlar deb qadnay algoritmlarga aytiladi?
Rabin algoritmida kalitlar qanday generatsiya qilinadi?
Rabin algoritmida xabarlarni qanday shifrlanadi?
Rabin algoritmida xabarlarni qanday deshifrlanadi?
Rabin algoritmining zaifligi qanday?