1-Мавзу: Очиқ калитли шифрлаш алгоритмлари Криптология кафедраси

Очиқ калитли криптотизимларда туб сонлар

Носимметрик криптотизимларда калит сифатида катта туб сон ёки катта туб сонларнинг кўпайтмаси бўлган сон олинади.

Мавжуд туб сонни генерациялаш алгоритмларида бир марта тасодифан танланган соннинг энг катта ва энг кичик битлари 1 га тенг қилиб олинади. Энг катта битнинг 1 га тенг қилиб олиниши туб соннинг зарур узунлигини таъминласа, энг кичик битнинг 1 га тенг бўлиши унинг тоқлигини таъминлайди. Кейин n нинг унча катта бўлмаган жадваллардан маълум бўлган: 3, 5, 7, 11, ... туб сонларга бўлиб кўрилади.

Барча мавжуд тубликка синаш алгоритмларини икки синфга бўлиш мумкин:

• аниқлаштирилган тестлар, - бу синов натижасида тадқиқ этилаётган сон тубми ёки тубмаслигини кафолатланган аниқ жавоби берилади;
• эҳтимолли тестлар, - бу синовнинг натижаси етарлича катта эҳтимоллик билан ҳақиқий бўлади. Битта сон учун турли параметрлар билан уларнинг кўп марталик такрорланиши хатолик бўлиши эҳтимоллигини етарлича кичик қийматли қилиш имконини беради.

Очиқ калитли криптотизимларда туб сонлар

Одатда, катта туб сонларни генерация қилишда қуйидаги ёндошувдан фойдаланилади:

• 1. Тасодифан берилган узунликдаги (битлар сони бўйича) тоқ сон n танланади.
• 2. Тубликка синаш (тест) ўтказилади.
• 3. Агар n мураккаб сон бўлса, у ҳолда 1-қадамга қайтилади.

Сонларни тубликка текширишнинг эҳтимоллик алгоритмлари

• Ферма тести
• Солавей Штрассен тести
• Рабби-Милнер тести
• Бейл-померенц тести
• Лукас тести
• Поклингтон тести
• Прот тести
• Фробениус

Ферманинг катта сонларни тубликка синаш алгоритми

Агар п- туб сон бўлса, у ҳолда “Ферманинг кичик теоремаси”га кўра тенглик ўринли бўлади, бунда а ихтиёрий ва п а га каррали эмас. тенгликни бажарилиши берилган п соннинг тублигини аниқловчи зарурий ва етарли шартдир. Яъни агар бирор бир а учун бўлса, у ҳолда п мураккаб сон бўлади, акс ҳолда эса бирор аниқ нарса айтиш қийин, аммо соннинг тублик эҳтимоли ортади. Агар мураккаб сон п учун таққослама бажарилса, у ҳолда п сон а асос бўйича псевдотуб дейилади.