5.2 Задача дискретного логарифмирования на эллиптической кривой В мультипликативной группе Zp*, задачей дискретного логарифма является задача, в которой даны элементы группы r и q и модуль p, и число k выражается из уравнения r = qk mod p. Если группа эллиптической кривой задана с использованием мультипликативного примечания, то задача дискретного логарифмирования в данном случае звучит так: даны точки P и Q, нужно найти число k из уравнения Pk = Q; k - дискретный логарифм Q по основанию P. Когда эллиптическая кривая задана используя примечание по сумме, то задача дискретного логарифма может быть задана так: даны точки P и Q, нужно найти значение k из уравнения Pk = Q. Пример: Определена эллиптическая кривая y2 = x3 + 9x + 17 над F23, Каков дискретный логарифм k точки Q = (4,5) по основанию P = (16,5)? Один из способов нахождения k нужно вычислить последовательность точек P до точки Q . первые несколько вычислений точки P: P = (16,5) 2P = (20,20) 3P = (14,14) 4P = (19,20) 5P = (13,10) 6P = (7,3) 7P = (8,7) 8P = (12,17) 9P = (4,5) получаем, что 9P = (4,5) = Q, дискретным логарифмом Q по основанию P это k = 9. В реальном применении значение k может быть достаточно большим, что его вычисление таким образом не возможно из-за огромного количества операций, которые нужно было бы проводить.

Copyright © Certicom Corp., 1997-2000. All rights reserved. Information subject to change. http://www.certicom.com