Бір бағыттағы функциялар

Ашық кілті бар асимметриялық криптографиялық жүйелердің концепциясы бір бағыттағы функцияларды қолдануға негізделген. Бір бағыттағы функцияны келесі жолмен анықтауға болады.

Бір бағытталған функция деп келесі қасиеттері бар f(x) функциясы аталады:

         - Х жиынындағы барлық х-тер үшін y = f(x) функциясының мәндерін есептеу алгоритмы бар;  y мәндері Y-те болады (X пен Y – кейбір еркін жиынтықтар);

          - f функциясын айналдыру алгоритмы жоқ, яғни f(x) = y теңдеуін х арқылы шешу мүмкін емес. Бұл қасиет келесіні білдіреді: көптеген Y -тағы y-тер үшін f(x) = y болатындай Х-тегі х-ты табу өте күрделі; сонымен бірге ең кемінде жалғыз осындай х бар болады деп есептеледі.

 Кері түрлендірудің тиімді алгоритмдерінің жоқ болғаны f функцияны бір бағыттағы функциялар класына қатыстырудың негізгі критерийі болып табылады.

Бір бағыттағы функцияның бірінші мысалы ретінде бүтін сандық көбейтуді қарастырайық. Тура есеп – өте үлкен екі р және q бүтін сандардың көбейтіндісін яғни  мәнін табу ЕЭМ үшін қиын есеп емес.

Кері есеп – үлкен бүтін санды көбейтінділерге жіктеу яғни үлкен бүтін  санның  р және q бөлгіштерін табу n-нің өте үлкен мәндері үшін практикалық шешілмейтін есеп болып табылады. Сандар теориясының қазіргі кездегі бағалаулары бойынша бүтін сан жуықтап  n ≈ 2⁶⁶⁴ және p ≈ q болғанда  n санын жіктеу үшін 10²³ операциялар саны қажет, есеп қазіргі кездегі ЕЭМ-дер үшін практикалық шешілмейді.

Бір бағыттағы функцияның келесі сипатты мысалы ретінде белгіленген негізі мен модулі бар модулді экспонентаны атауға болады.

Онда негізі а болатын  n бойынша модулді экспонента келесідей функция болып табылады:

мұнда х – бүтін сан, 

Егер де у = а^х, онда, әрине, келесіні жазуға болады  х = log_a (у).

Сондықтан f_a,n(x) функцияны кері айналдыру есебі дискретті логарифмді табу немесе дискретті логарифмдеу есебі деп аталады.

Дискретті логарифмдеу есебі келесідей қойылады: белгілі бүтін a, n, у үшін  орындалатындай бүтін х санды табу керек.

Қабылдауға болатын уақытта дискретті логарифмді есептеудің алгоритмі әзірше табылмады. Сондықтан модулдік логарифм бір бағыттағы функция болып есептеледі.

   Дәріс мазмұны: ашық кілті бар алгоритмдер.