PolarSSL v1.3.7
dhm.c
Go to the documentation of this file.
1 /*
2  * Diffie-Hellman-Merkle key exchange
3  *
4  * Copyright (C) 2006-2014, Brainspark B.V.
5  *
6  * This file is part of PolarSSL (http://www.polarssl.org)
7  * Lead Maintainer: Paul Bakker <polarssl_maintainer at polarssl.org>
8  *
9  * All rights reserved.
10  *
11  * This program is free software; you can redistribute it and/or modify
12  * it under the terms of the GNU General Public License as published by
13  * the Free Software Foundation; either version 2 of the License, or
14  * (at your option) any later version.
15  *
16  * This program is distributed in the hope that it will be useful,
17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19  * GNU General Public License for more details.
20  *
21  * You should have received a copy of the GNU General Public License along
22  * with this program; if not, write to the Free Software Foundation, Inc.,
23  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
24  */
25 /*
26  * Reference:
27  *
28  * http://www.cacr.math.uwaterloo.ca/hac/ (chapter 12)
29  */
30 
31 #if !defined(POLARSSL_CONFIG_FILE)
32 #include "polarssl/config.h"
33 #else
34 #include POLARSSL_CONFIG_FILE
35 #endif
36 
37 #if defined(POLARSSL_DHM_C)
38 
39 #include "polarssl/dhm.h"
40 
41 #if defined(POLARSSL_PEM_PARSE_C)
42 #include "polarssl/pem.h"
43 #endif
44 
45 #if defined(POLARSSL_ASN1_PARSE_C)
46 #include "polarssl/asn1.h"
47 #endif
48 
49 #if defined(POLARSSL_PLATFORM_C)
50 #include "polarssl/platform.h"
51 #else
52 #include <stdlib.h>
53 #define polarssl_printf printf
54 #define polarssl_malloc malloc
55 #define polarssl_free free
56 #endif
57 
58 /*
59  * helper to validate the mpi size and import it
60  */
61 static int dhm_read_bignum( mpi *X,
62  unsigned char **p,
63  const unsigned char *end )
64 {
65  int ret, n;
66 
67  if( end - *p < 2 )
69 
70  n = ( (*p)[0] << 8 ) | (*p)[1];
71  (*p) += 2;
72 
73  if( (int)( end - *p ) < n )
75 
76  if( ( ret = mpi_read_binary( X, *p, n ) ) != 0 )
78 
79  (*p) += n;
80 
81  return( 0 );
82 }
83 
84 /*
85  * Verify sanity of parameter with regards to P
86  *
87  * Parameter should be: 2 <= public_param <= P - 2
88  *
89  * For more information on the attack, see:
90  * http://www.cl.cam.ac.uk/~rja14/Papers/psandqs.pdf
91  * http://web.nvd.nist.gov/view/vuln/detail?vulnId=CVE-2005-2643
92  */
93 static int dhm_check_range( const mpi *param, const mpi *P )
94 {
95  mpi L, U;
97 
98  mpi_init( &L ); mpi_init( &U );
99 
100  MPI_CHK( mpi_lset( &L, 2 ) );
101  MPI_CHK( mpi_sub_int( &U, P, 2 ) );
102 
103  if( mpi_cmp_mpi( param, &L ) >= 0 &&
104  mpi_cmp_mpi( param, &U ) <= 0 )
105  {
106  ret = 0;
107  }
108 
109 cleanup:
110  mpi_free( &L ); mpi_free( &U );
111  return( ret );
112 }
113 
114 /*
115  * Parse the ServerKeyExchange parameters
116  */
117 int dhm_read_params( dhm_context *ctx,
118  unsigned char **p,
119  const unsigned char *end )
120 {
121  int ret;
122 
123  dhm_free( ctx );
124 
125  if( ( ret = dhm_read_bignum( &ctx->P, p, end ) ) != 0 ||
126  ( ret = dhm_read_bignum( &ctx->G, p, end ) ) != 0 ||
127  ( ret = dhm_read_bignum( &ctx->GY, p, end ) ) != 0 )
128  return( ret );
129 
130  if( ( ret = dhm_check_range( &ctx->GY, &ctx->P ) ) != 0 )
131  return( ret );
132 
133  ctx->len = mpi_size( &ctx->P );
134 
135  return( 0 );
136 }
137 
138 /*
139  * Setup and write the ServerKeyExchange parameters
140  */
141 int dhm_make_params( dhm_context *ctx, int x_size,
142  unsigned char *output, size_t *olen,
143  int (*f_rng)(void *, unsigned char *, size_t),
144  void *p_rng )
145 {
146  int ret, count = 0;
147  size_t n1, n2, n3;
148  unsigned char *p;
149 
150  if( mpi_cmp_int( &ctx->P, 0 ) == 0 )
152 
153  /*
154  * Generate X as large as possible ( < P )
155  */
156  do
157  {
158  mpi_fill_random( &ctx->X, x_size, f_rng, p_rng );
159 
160  while( mpi_cmp_mpi( &ctx->X, &ctx->P ) >= 0 )
161  MPI_CHK( mpi_shift_r( &ctx->X, 1 ) );
162 
163  if( count++ > 10 )
165  }
166  while( dhm_check_range( &ctx->X, &ctx->P ) != 0 );
167 
168  /*
169  * Calculate GX = G^X mod P
170  */
171  MPI_CHK( mpi_exp_mod( &ctx->GX, &ctx->G, &ctx->X,
172  &ctx->P , &ctx->RP ) );
173 
174  if( ( ret = dhm_check_range( &ctx->GX, &ctx->P ) ) != 0 )
175  return( ret );
176 
177  /*
178  * export P, G, GX
179  */
180 #define DHM_MPI_EXPORT(X,n) \
181  MPI_CHK( mpi_write_binary( X, p + 2, n ) ); \
182  *p++ = (unsigned char)( n >> 8 ); \
183  *p++ = (unsigned char)( n ); p += n;
184 
185  n1 = mpi_size( &ctx->P );
186  n2 = mpi_size( &ctx->G );
187  n3 = mpi_size( &ctx->GX );
188 
189  p = output;
190  DHM_MPI_EXPORT( &ctx->P , n1 );
191  DHM_MPI_EXPORT( &ctx->G , n2 );
192  DHM_MPI_EXPORT( &ctx->GX, n3 );
193 
194  *olen = p - output;
195 
196  ctx->len = n1;
197 
198 cleanup:
199 
200  if( ret != 0 )
201  return( POLARSSL_ERR_DHM_MAKE_PARAMS_FAILED + ret );
202 
203  return( 0 );
204 }
205 
206 /*
207  * Import the peer's public value G^Y
208  */
209 int dhm_read_public( dhm_context *ctx,
210  const unsigned char *input, size_t ilen )
211 {
212  int ret;
213 
214  if( ctx == NULL || ilen < 1 || ilen > ctx->len )
216 
217  if( ( ret = mpi_read_binary( &ctx->GY, input, ilen ) ) != 0 )
218  return( POLARSSL_ERR_DHM_READ_PUBLIC_FAILED + ret );
219 
220  return( 0 );
221 }
222 
223 /*
224  * Create own private value X and export G^X
225  */
226 int dhm_make_public( dhm_context *ctx, int x_size,
227  unsigned char *output, size_t olen,
228  int (*f_rng)(void *, unsigned char *, size_t),
229  void *p_rng )
230 {
231  int ret, count = 0;
232 
233  if( ctx == NULL || olen < 1 || olen > ctx->len )
235 
236  if( mpi_cmp_int( &ctx->P, 0 ) == 0 )
238 
239  /*
240  * generate X and calculate GX = G^X mod P
241  */
242  do
243  {
244  mpi_fill_random( &ctx->X, x_size, f_rng, p_rng );
245 
246  while( mpi_cmp_mpi( &ctx->X, &ctx->P ) >= 0 )
247  MPI_CHK( mpi_shift_r( &ctx->X, 1 ) );
248 
249  if( count++ > 10 )
251  }
252  while( dhm_check_range( &ctx->X, &ctx->P ) != 0 );
253 
254  MPI_CHK( mpi_exp_mod( &ctx->GX, &ctx->G, &ctx->X,
255  &ctx->P , &ctx->RP ) );
256 
257  if( ( ret = dhm_check_range( &ctx->GX, &ctx->P ) ) != 0 )
258  return( ret );
259 
260  MPI_CHK( mpi_write_binary( &ctx->GX, output, olen ) );
261 
262 cleanup:
263 
264  if( ret != 0 )
265  return( POLARSSL_ERR_DHM_MAKE_PUBLIC_FAILED + ret );
266 
267  return( 0 );
268 }
269 
270 /*
271  * Use the blinding method and optimisation suggested in section 10 of:
272  * KOCHER, Paul C. Timing attacks on implementations of Diffie-Hellman, RSA,
273  * DSS, and other systems. In : Advances in Cryptology—CRYPTO’96. Springer
274  * Berlin Heidelberg, 1996. p. 104-113.
275  */
276 static int dhm_update_blinding( dhm_context *ctx,
277  int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
278 {
279  int ret, count;
280 
281  /*
282  * Don't use any blinding the first time a particular X is used,
283  * but remember it to use blinding next time.
284  */
285  if( mpi_cmp_mpi( &ctx->X, &ctx->pX ) != 0 )
286  {
287  MPI_CHK( mpi_copy( &ctx->pX, &ctx->X ) );
288  MPI_CHK( mpi_lset( &ctx->Vi, 1 ) );
289  MPI_CHK( mpi_lset( &ctx->Vf, 1 ) );
290 
291  return( 0 );
292  }
293 
294  /*
295  * Ok, we need blinding. Can we re-use existing values?
296  * If yes, just update them by squaring them.
297  */
298  if( mpi_cmp_int( &ctx->Vi, 1 ) != 0 )
299  {
300  MPI_CHK( mpi_mul_mpi( &ctx->Vi, &ctx->Vi, &ctx->Vi ) );
301  MPI_CHK( mpi_mod_mpi( &ctx->Vi, &ctx->Vi, &ctx->P ) );
302 
303  MPI_CHK( mpi_mul_mpi( &ctx->Vf, &ctx->Vf, &ctx->Vf ) );
304  MPI_CHK( mpi_mod_mpi( &ctx->Vf, &ctx->Vf, &ctx->P ) );
305 
306  return( 0 );
307  }
308 
309  /*
310  * We need to generate blinding values from scratch
311  */
312 
313  /* Vi = random( 2, P-1 ) */
314  count = 0;
315  do
316  {
317  mpi_fill_random( &ctx->Vi, mpi_size( &ctx->P ), f_rng, p_rng );
318 
319  while( mpi_cmp_mpi( &ctx->Vi, &ctx->P ) >= 0 )
320  MPI_CHK( mpi_shift_r( &ctx->Vi, 1 ) );
321 
322  if( count++ > 10 )
324  }
325  while( mpi_cmp_int( &ctx->Vi, 1 ) <= 0 );
326 
327  /* Vf = Vi^-X mod P */
328  MPI_CHK( mpi_inv_mod( &ctx->Vf, &ctx->Vi, &ctx->P ) );
329  MPI_CHK( mpi_exp_mod( &ctx->Vf, &ctx->Vf, &ctx->X, &ctx->P, &ctx->RP ) );
330 
331 cleanup:
332  return( ret );
333 }
334 
335 /*
336  * Derive and export the shared secret (G^Y)^X mod P
337  */
338 int dhm_calc_secret( dhm_context *ctx,
339  unsigned char *output, size_t *olen,
340  int (*f_rng)(void *, unsigned char *, size_t),
341  void *p_rng )
342 {
343  int ret;
344  mpi GYb;
345 
346  if( ctx == NULL || *olen < ctx->len )
348 
349  if( ( ret = dhm_check_range( &ctx->GY, &ctx->P ) ) != 0 )
350  return( ret );
351 
352  mpi_init( &GYb );
353 
354  /* Blind peer's value */
355  if( f_rng != NULL )
356  {
357  MPI_CHK( dhm_update_blinding( ctx, f_rng, p_rng ) );
358  MPI_CHK( mpi_mul_mpi( &GYb, &ctx->GY, &ctx->Vi ) );
359  MPI_CHK( mpi_mod_mpi( &GYb, &GYb, &ctx->P ) );
360  }
361  else
362  MPI_CHK( mpi_copy( &GYb, &ctx->GY ) );
363 
364  /* Do modular exponentiation */
365  MPI_CHK( mpi_exp_mod( &ctx->K, &GYb, &ctx->X,
366  &ctx->P, &ctx->RP ) );
367 
368  /* Unblind secret value */
369  if( f_rng != NULL )
370  {
371  MPI_CHK( mpi_mul_mpi( &ctx->K, &ctx->K, &ctx->Vf ) );
372  MPI_CHK( mpi_mod_mpi( &ctx->K, &ctx->K, &ctx->P ) );
373  }
374 
375  *olen = mpi_size( &ctx->K );
376 
377  MPI_CHK( mpi_write_binary( &ctx->K, output, *olen ) );
378 
379 cleanup:
380  mpi_free( &GYb );
381 
382  if( ret != 0 )
383  return( POLARSSL_ERR_DHM_CALC_SECRET_FAILED + ret );
384 
385  return( 0 );
386 }
387 
388 /*
389  * Free the components of a DHM key
390  */
391 void dhm_free( dhm_context *ctx )
392 {
393  mpi_free( &ctx->pX); mpi_free( &ctx->Vf ); mpi_free( &ctx->Vi );
394  mpi_free( &ctx->RP ); mpi_free( &ctx->K ); mpi_free( &ctx->GY );
395  mpi_free( &ctx->GX ); mpi_free( &ctx->X ); mpi_free( &ctx->G );
396  mpi_free( &ctx->P );
397 
398  memset( ctx, 0, sizeof( dhm_context ) );
399 }
400 
401 #if defined(POLARSSL_ASN1_PARSE_C)
402 /*
403  * Parse DHM parameters
404  */
405 int dhm_parse_dhm( dhm_context *dhm, const unsigned char *dhmin,
406  size_t dhminlen )
407 {
408  int ret;
409  size_t len;
410  unsigned char *p, *end;
411 #if defined(POLARSSL_PEM_PARSE_C)
412  pem_context pem;
413 
414  pem_init( &pem );
415  memset( dhm, 0, sizeof( dhm_context ) );
416 
417  ret = pem_read_buffer( &pem,
418  "-----BEGIN DH PARAMETERS-----",
419  "-----END DH PARAMETERS-----",
420  dhmin, NULL, 0, &dhminlen );
421 
422  if( ret == 0 )
423  {
424  /*
425  * Was PEM encoded
426  */
427  dhminlen = pem.buflen;
428  }
430  goto exit;
431 
432  p = ( ret == 0 ) ? pem.buf : (unsigned char *) dhmin;
433 #else
434  p = (unsigned char *) dhmin;
435 #endif /* POLARSSL_PEM_PARSE_C */
436  end = p + dhminlen;
437 
438  /*
439  * DHParams ::= SEQUENCE {
440  * prime INTEGER, -- P
441  * generator INTEGER, -- g
442  * }
443  */
444  if( ( ret = asn1_get_tag( &p, end, &len,
445  ASN1_CONSTRUCTED | ASN1_SEQUENCE ) ) != 0 )
446  {
448  goto exit;
449  }
450 
451  end = p + len;
452 
453  if( ( ret = asn1_get_mpi( &p, end, &dhm->P ) ) != 0 ||
454  ( ret = asn1_get_mpi( &p, end, &dhm->G ) ) != 0 )
455  {
457  goto exit;
458  }
459 
460  if( p != end )
461  {
464  goto exit;
465  }
466 
467  ret = 0;
468 
469  dhm->len = mpi_size( &dhm->P );
470 
471 exit:
472 #if defined(POLARSSL_PEM_PARSE_C)
473  pem_free( &pem );
474 #endif
475  if( ret != 0 )
476  dhm_free( dhm );
477 
478  return( ret );
479 }
480 
481 #if defined(POLARSSL_FS_IO)
482 /*
483  * Load all data from a file into a given buffer.
484  */
485 static int load_file( const char *path, unsigned char **buf, size_t *n )
486 {
487  FILE *f;
488  long size;
489 
490  if( ( f = fopen( path, "rb" ) ) == NULL )
492 
493  fseek( f, 0, SEEK_END );
494  if( ( size = ftell( f ) ) == -1 )
495  {
496  fclose( f );
498  }
499  fseek( f, 0, SEEK_SET );
500 
501  *n = (size_t) size;
502 
503  if( *n + 1 == 0 ||
504  ( *buf = (unsigned char *) polarssl_malloc( *n + 1 ) ) == NULL )
505  {
506  fclose( f );
508  }
509 
510  if( fread( *buf, 1, *n, f ) != *n )
511  {
512  fclose( f );
513  polarssl_free( *buf );
515  }
516 
517  fclose( f );
518 
519  (*buf)[*n] = '\0';
520 
521  return( 0 );
522 }
523 
524 /*
525  * Load and parse DHM parameters
526  */
527 int dhm_parse_dhmfile( dhm_context *dhm, const char *path )
528 {
529  int ret;
530  size_t n;
531  unsigned char *buf;
532 
533  if ( ( ret = load_file( path, &buf, &n ) ) != 0 )
534  return( ret );
535 
536  ret = dhm_parse_dhm( dhm, buf, n );
537 
538  memset( buf, 0, n + 1 );
539  polarssl_free( buf );
540 
541  return( ret );
542 }
543 #endif /* POLARSSL_FS_IO */
544 #endif /* POLARSSL_ASN1_PARSE_C */
545 
546 #if defined(POLARSSL_SELF_TEST)
547 
548 #include "polarssl/certs.h"
549 
550 /*
551  * Checkup routine
552  */
553 int dhm_self_test( int verbose )
554 {
555 #if defined(POLARSSL_CERTS_C)
556  int ret;
557  dhm_context dhm;
558 
559  if( verbose != 0 )
560  polarssl_printf( " DHM parameter load: " );
561 
562  if( ( ret = dhm_parse_dhm( &dhm, (const unsigned char *) test_dhm_params,
563  strlen( test_dhm_params ) ) ) != 0 )
564  {
565  if( verbose != 0 )
566  polarssl_printf( "failed\n" );
567 
568  return( ret );
569  }
570 
571  if( verbose != 0 )
572  polarssl_printf( "passed\n\n" );
573 
574  dhm_free( &dhm );
575 
576  return( 0 );
577 #else
578  if( verbose != 0 )
579  polarssl_printf( " DHM parameter load: skipped\n" );
580 
581  return( 0 );
582 #endif /* POLARSSL_CERTS_C */
583 }
584 
585 #endif /* POLARSSL_SELF_TEST */
586 
587 #endif /* POLARSSL_DHM_C */
int mpi_cmp_int(const mpi *X, t_sint z)
Compare signed values.
#define POLARSSL_ERR_DHM_MAKE_PUBLIC_FAILED
Making of the public value failed.
Definition: dhm.h:39
mpi P
Definition: dhm.h:146
#define POLARSSL_ERR_DHM_MAKE_PARAMS_FAILED
Making of the DHM parameters failed.
Definition: dhm.h:37
#define POLARSSL_ERR_DHM_INVALID_FORMAT
The ASN.1 data is not formatted correctly.
Definition: dhm.h:41
#define POLARSSL_ERR_ASN1_LENGTH_MISMATCH
Actual length differs from expected length.
Definition: asn1.h:57
DHM context structure.
Definition: dhm.h:143
#define POLARSSL_ERR_DHM_CALC_SECRET_FAILED
Calculation of the DHM secret failed.
Definition: dhm.h:40
int mpi_fill_random(mpi *X, size_t size, int(*f_rng)(void *, unsigned char *, size_t), void *p_rng)
Fill an MPI X with size bytes of random.
#define POLARSSL_ERR_DHM_MALLOC_FAILED
Allocation of memory failed.
Definition: dhm.h:42
int dhm_self_test(int verbose)
Checkup routine.
mpi GX
Definition: dhm.h:149
#define polarssl_free
Definition: platform.h:91
#define ASN1_SEQUENCE
Definition: asn1.h:82
Configuration options (set of defines)
mpi X
Definition: dhm.h:148
#define ASN1_CONSTRUCTED
Definition: asn1.h:92
int mpi_lset(mpi *X, t_sint z)
Set value from integer.
MPI structure.
Definition: bignum.h:181
PolarSSL Platform abstraction layer.
void mpi_init(mpi *X)
Initialize one MPI.
int mpi_cmp_mpi(const mpi *X, const mpi *Y)
Compare signed values.
size_t len
Definition: dhm.h:145
int mpi_shift_r(mpi *X, size_t count)
Right-shift: X &gt;&gt;= count.
int dhm_read_params(dhm_context *ctx, unsigned char **p, const unsigned char *end)
Parse the ServerKeyExchange parameters.
Generic ASN.1 parsing.
#define POLARSSL_ERR_DHM_READ_PUBLIC_FAILED
Reading of the public values failed.
Definition: dhm.h:38
Privacy Enhanced Mail (PEM) decoding.
mpi G
Definition: dhm.h:147
#define POLARSSL_ERR_DHM_READ_PARAMS_FAILED
Reading of the DHM parameters failed.
Definition: dhm.h:36
int mpi_inv_mod(mpi *X, const mpi *A, const mpi *N)
Modular inverse: X = A^-1 mod N.
mpi GY
Definition: dhm.h:150
void mpi_free(mpi *X)
Unallocate one MPI.
Diffie-Hellman-Merkle key exchange.
int mpi_exp_mod(mpi *X, const mpi *A, const mpi *E, const mpi *N, mpi *_RR)
Sliding-window exponentiation: X = A^E mod N.
mpi K
Definition: dhm.h:151
mpi RP
Definition: dhm.h:152
int mpi_read_binary(mpi *X, const unsigned char *buf, size_t buflen)
Import X from unsigned binary data, big endian.
mpi Vi
Definition: dhm.h:153
Sample certificates and DHM parameters for testing.
int dhm_make_public(dhm_context *ctx, int x_size, unsigned char *output, size_t olen, int(*f_rng)(void *, unsigned char *, size_t), void *p_rng)
Create own private value X and export G^X.
size_t mpi_size(const mpi *X)
Return the total size in bytes.
#define POLARSSL_ERR_DHM_FILE_IO_ERROR
Read/write of file failed.
Definition: dhm.h:43
int mpi_copy(mpi *X, const mpi *Y)
Copy the contents of Y into X.
int mpi_mod_mpi(mpi *R, const mpi *A, const mpi *B)
Modulo: R = A mod B.
int asn1_get_tag(unsigned char **p, const unsigned char *end, size_t *len, int tag)
Get the tag and length of the tag.
#define polarssl_printf
Definition: platform.h:109
int mpi_write_binary(const mpi *X, unsigned char *buf, size_t buflen)
Export X into unsigned binary data, big endian.
int dhm_parse_dhm(dhm_context *dhm, const unsigned char *dhmin, size_t dhminlen)
Parse DHM parameters.
void dhm_free(dhm_context *ctx)
Free the components of a DHM key.
#define POLARSSL_ERR_DHM_BAD_INPUT_DATA
Bad input parameters to function.
Definition: dhm.h:35
#define POLARSSL_ERR_PEM_NO_HEADER_FOOTER_PRESENT
No PEM header or footer found.
Definition: pem.h:38
int mpi_mul_mpi(mpi *X, const mpi *A, const mpi *B)
Baseline multiplication: X = A * B.
#define polarssl_malloc
Definition: platform.h:90
mpi pX
Definition: dhm.h:155
int asn1_get_mpi(unsigned char **p, const unsigned char *end, mpi *X)
Retrieve a MPI value from an integer ASN.1 tag.
int mpi_sub_int(mpi *X, const mpi *A, t_sint b)
Signed subtraction: X = A - b.
mpi Vf
Definition: dhm.h:154
int dhm_parse_dhmfile(dhm_context *dhm, const char *path)
Load and parse DHM parameters.
int dhm_make_params(dhm_context *ctx, int x_size, unsigned char *output, size_t *olen, int(*f_rng)(void *, unsigned char *, size_t), void *p_rng)
Setup and write the ServerKeyExchange parameters.
#define POLARSSL_ERR_MPI_NOT_ACCEPTABLE
The input arguments are not acceptable.
Definition: bignum.h:62
int dhm_read_public(dhm_context *ctx, const unsigned char *input, size_t ilen)
Import the peer&#39;s public value G^Y.
#define MPI_CHK(f)
Definition: bignum.h:65
int dhm_calc_secret(dhm_context *ctx, unsigned char *output, size_t *olen, int(*f_rng)(void *, unsigned char *, size_t), void *p_rng)
Derive and export the shared secret (G^Y)^X mod P.