{"id":14771,"date":"2022-05-28T19:53:40","date_gmt":"2022-05-28T23:53:40","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=14771"},"modified":"2026-06-09T11:04:00","modified_gmt":"2026-06-09T15:04:00","slug":"tr-165-key-exchange-using-chebychev-polynomials","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1990\/tr-165-key-exchange-using-chebychev-polynomials\/","title":{"rendered":"TR-165: Key Exchange Using Chebychev Polynomials"},"content":{"rendered":"\n
\n
\n\n
\n
\n
\n

\n TR-165: Key Exchange Using Chebychev Polynomials\n <\/h1>\n \n \n <\/header>\n\n <\/div>\n\n <\/div>\n\n <\/div>\n<\/section>\n\n\n\n

Carleton University
Technical Report<\/a> TR-165<\/strong>
January 1990<\/p>\n\n\n\n

Key Exchange Using Chebychev Polynomials<\/h2>\n\n\n\n

M.D. Atkinson & Vincenzo Acciaro<\/p>\n\n\n\n

Abstract<\/h3>\n\n\n\n

The well-known Diffie-Hellman protocol for key exchange LDin6] allows two parties to agree on a secret key without the key being sent along an insecure communication channel. This protocol is a special case of the following general scheme which allows two parties A and B to agree on an element of a key space K. Let F = {Fml m=0,1,2, \u2026. } and G = {Gnl n=0,1,2, \u2026. } be two families of functions defined on K having the property that for all m, n we have the equality F (Fn(x))=Fn(Fm(x)). Initially A and B agree on an element a E K which may be made public. Next, A chooses a private integer m and sends Fm(<X) to B while B chooses a private integer n and sends Gn(<X) to A Finally A computes Fm(G0(a)) while B computes G (Fm(<X)); by the assumption on F and G these two results are equal and serve as their common key. In all the examples given in this paper F = G and we shall assume this from now on; it would however be interesting to have examples where Ft= G. In the original Diffie\u00adHellman scheme F and G were each the set of functions {x-nm mod p, m=O, 1,2,3 \u2026 } (where pis prime) and K was the field Zp of integers modulo p. In [Rue88l F and G consisted of the functional powers of some function p(x). The condition that members of F commute with one another under functional composition is a very restrictive one. However there is another family of polynomials which commute under composition:- the Chebychev polynomials. Indeed it is readily seen that, if T 0 (x) = cos(m arccos x ), we have
Tm(T 0(x)) = cos(m arccos (cos (n arccos x )) = cos(mn arccos x) = T1110(x)
A basic recurrence, following from properties of the cosine function, relating the Chebychev polynomials is Tn+1(a) \u2013 2a T0(a) + T0_1(<X) = 0<\/p>\n\n\n\n

Since the Chebychev polynomials have integer coefficients we may regard them ils polynomials defined on Zp and the above equations still hold (and from now on we shall use arithmetic modulo p ). In order for the Chebychev polynomials to yield a practical method for key exchange it is essential that Tn(a) be computable rapidly, that a be chosen so that there is a large collection of potential keys which may be generated by the algorithm, and that it should not be feasible to deduce n given the value of T0(a) (which can be intercepted by an enemy during the key exchange protocol).<\/p>\n\n\n\n

TR-165.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"

Carleton UniversityTechnical Report TR-165January 1990 Key Exchange Using Chebychev Polynomials M.D. Atkinson & Vincenzo Acciaro Abstract The well-known Diffie-Hellman protocol for key exchange LDin6] allows two parties to agree on a secret key without the key being sent along an insecure communication channel. This protocol is a special case of the following general scheme which allows […]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":11906,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_acf_changed":false,"_cu_dining_location_slug":"","footnotes":"","_links_to":"","_links_to_target":""},"cu_page_type":[],"class_list":["post-14771","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":""},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/14771","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/comments?post=14771"}],"version-history":[{"count":3,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/14771\/revisions"}],"predecessor-version":[{"id":24546,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/14771\/revisions\/24546"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/11906"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=14771"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=14771"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}