{VERSION 3 0 "IBM INTEL NT" "3.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 1 12 128 0 128 1 0 1 0 0 1 0 0 0 0 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 }{CSTYLE "2D Output" 2 20 "Times" 1 12 0 128 0 1 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 256 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 257 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 258 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 259 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 260 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 261 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 262 "" 1 14 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 263 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 264 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE " " -1 265 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 266 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 267 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 268 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 269 "" 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 270 "" 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 271 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 272 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 273 "" 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 274 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 275 "" 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 276 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 277 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 278 "" 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 279 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 280 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 282 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 283 "" 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 284 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 285 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 286 "" 1 14 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 287 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 288 "" 1 14 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 289 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE " " -1 290 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 291 "" 0 1 0 0 0 0 0 2 0 0 0 0 0 0 0 }{CSTYLE "" -1 292 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 293 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 294 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 295 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 296 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 297 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 298 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 299 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 300 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 301 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 302 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 303 "" 1 14 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 304 "" 1 14 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 305 "" 1 14 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 306 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 307 "" 1 14 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 308 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 309 "" 1 14 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 310 "" 1 14 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 311 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 312 "" 1 14 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 313 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 314 "" 1 14 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE " " -1 315 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 316 "" 1 14 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 317 "" 1 14 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 318 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 319 "" 1 14 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 320 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 321 "" 1 14 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 322 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 323 "" 1 14 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE " " -1 324 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 325 "" 1 14 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 326 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 327 "" 1 14 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 328 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 329 "" 1 14 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 330 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 331 "" 1 14 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 332 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE " " -1 333 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 334 "" 1 14 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 335 "" 1 14 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 336 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 337 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 338 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 339 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 340 "" 1 14 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 341 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE " " -1 342 "" 1 14 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 343 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 344 "" 1 14 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 345 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 346 "" 1 14 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 347 "" 1 14 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 348 "" 1 14 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 349 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 350 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE " " -1 351 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 352 "" 1 14 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 353 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 354 "" 1 14 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 355 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 356 "" 1 14 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 357 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 358 "" 1 14 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 359 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE " " -1 360 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 361 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 362 "" 1 14 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 363 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 364 "" 1 14 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 365 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 366 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 367 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 368 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 369 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 370 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 371 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 372 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 373 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 374 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 375 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 376 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 377 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 378 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 379 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 380 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 381 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 382 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 383 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 384 "" 1 14 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 385 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 386 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 387 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 388 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 389 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 390 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 391 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 392 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 393 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 394 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 395 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 396 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 397 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 398 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 399 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 400 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 401 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 402 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 403 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 404 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 405 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 406 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 407 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 408 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 409 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 410 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 411 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 412 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 413 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 414 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 415 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 416 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 417 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 418 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 419 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 420 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 421 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 422 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 423 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 424 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 425 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 426 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 427 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 428 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 429 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 430 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 431 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 432 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 433 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 434 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 435 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 436 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 437 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 438 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 439 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 440 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 441 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 442 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 443 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 444 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 445 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 446 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 447 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 448 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 449 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 450 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 451 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 452 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 453 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 454 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 455 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 456 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 457 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 458 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 459 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 460 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 461 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 462 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 463 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 464 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 465 "" 1 18 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 466 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 467 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 468 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 469 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 470 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 471 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 472 "" 1 14 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 473 "" 1 14 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 474 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 475 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 476 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 477 "" 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 478 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 479 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 480 "Helvetica" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 } {PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 128 1 2 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Maple Output" 0 11 1 {CSTYLE "" -1 -1 "Courier" 1 12 0 128 0 1 0 1 0 0 0 0 0 0 0 }3 3 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 11 12 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 } {PSTYLE "Bullet Item" 0 15 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 3 3 0 0 0 0 0 0 15 2 }{PSTYLE "Title" 0 18 1 {CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 1 1 0 0 0 0 0 0 }3 0 0 -1 12 12 0 0 0 0 0 0 19 0 }{PSTYLE "R3 Font 0" -1 256 1 {CSTYLE "" -1 -1 "Helveti ca" 1 12 128 0 128 1 2 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 2" -1 257 1 {CSTYLE "" -1 -1 "Courier" 1 12 0 128 0 1 2 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 258 1 {CSTYLE "" -1 -1 "" 1 18 0 0 0 0 1 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 259 1 {CSTYLE "" -1 -1 "" 1 10 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "# codes20_dig.msw" } }}{EXCHG {PARA 18 "" 0 "" {TEXT 257 18 "Digital signatures" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 5 "This " }{TEXT 262 5 "Maple" }{TEXT 263 0 "" }{TEXT -1 22 " worksheet treats the " } {TEXT 260 29 "fundamentally important topic" }{TEXT -1 3 " of" }} {PARA 0 "" 0 "" {TEXT 258 19 "digital signature. " }{TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 264 14 "Press coverage" }{TEXT -1 54 ". In recent years hardly a day h as passed without some" }}{PARA 0 "" 0 "" {TEXT -1 62 "newspaper/magaz ine/journal make some reference to 'e-commerce'" }}{PARA 0 "" 0 "" {TEXT -1 31 "and the associated concepts of " }{TEXT 265 10 "encryptio n" }{TEXT -1 2 ", " }{TEXT 266 11 "decryption " }{TEXT -1 4 "and " } {TEXT 268 14 "secure digital" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 267 10 "signatures" }{TEXT -1 60 " (in short, the whole paraphernalia \+ of modern cryptography)." }}{PARA 0 "" 0 "" {TEXT -1 75 "For us - livi ng in Ireland - the most newsworthy recent event in connection" }} {PARA 0 "" 0 "" {TEXT -1 30 "with e-commerce has been the \"" }{TEXT 269 36 "Digital history made in Dublin plant" }{TEXT -1 5 "\", as" }} {PARA 0 "" 0 "" {TEXT -1 16 "reported in the " }{TEXT 270 11 "Irish Ti mes" }{TEXT 271 0 "" }{TEXT -1 46 " on Saturday, 5th. September (1998) , which was" }}{PARA 0 "" 0 "" {TEXT -1 23 "also the subject of an " } {TEXT 272 0 "" }{TEXT 273 11 "Irish Times" }{TEXT 274 0 "" }{TEXT -1 12 " editorial \"" }{TEXT 275 15 "Digital dawning" }{TEXT 276 1 "\"" } {TEXT -1 11 " (the event" }}{PARA 0 "" 0 "" {TEXT -1 71 "itself was co vered 'live' on RTE television on Friday, 4th. September)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 4 "The " }{TEXT 277 5 "event" }{TEXT -1 18 " was the historic " }{TEXT 278 16 "digitally s igned" }{TEXT -1 32 " joint communique on e-commerce," }}{PARA 0 "" 0 "" {TEXT -1 67 "performed by the US President, Mr. Clinton, and the he ad of our own" }}{PARA 0 "" 0 "" {TEXT -1 71 "government, Mr. Ahern (o ur neighbour here in Drumcondra). For the press" }}{PARA 0 "" 0 "" {TEXT -1 72 "cuttings see the Mathematics notice-board opposite my off ice in E-block." }}{PARA 0 "" 0 "" {TEXT -1 45 "The software used in t he signing ceremony at " }{TEXT 279 7 "Gateway" }{TEXT -1 20 " (one of the largest" }}{PARA 0 "" 0 "" {TEXT -1 72 "US computer firms, whose \+ European headquarters is here in Dublin, and on" }}{PARA 0 "" 0 "" {TEXT -1 71 "one of whose computers I am preparing these notes for you ) was provided" }}{PARA 0 "" 0 "" {TEXT -1 43 "by the Irish cryptograp hy software company " }{TEXT 280 22 "Baltimore Technologies" }{TEXT -1 7 ", which" }}{PARA 0 "" 0 "" {TEXT -1 55 "has its headquarters in \+ the Financial Services Centre. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 282 27 "Now for the Mathematics o f " }{TEXT 283 17 "digital signature" }{TEXT 284 0 "" }{TEXT -1 28 ". \+ Strictly speaking it's the" }}{PARA 0 "" 0 "" {TEXT -1 54 "RSA cryptog raphic method used as a means of providing " }{TEXT 285 18 "digital si gnatures" }{TEXT -1 1 "." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 74 "First recall the usual steps and standard notation s you will have already " }}{PARA 0 "" 0 "" {TEXT -1 56 "encountered i n relation to the RSA cryptographic method:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 15 "" 0 "" {TEXT -1 0 "" }{TEXT 304 6 "Choose" }{TEXT 336 9 " (in the " }{TEXT 305 10 "real world" }{TEXT 306 25 ", care is \+ needed) primes " }{TEXT 307 1 "p" }{TEXT 308 5 " and " }{TEXT 309 1 "q " }{TEXT 360 3 ", \n" }{TEXT 286 3 "set" }{TEXT 337 1 " " }{TEXT 310 1 "n" }{TEXT 311 3 " = " }{TEXT 312 1 "p" }{TEXT 313 1 "*" }{TEXT 314 1 "q" }{TEXT 315 14 ", forming the " }{TEXT 316 14 "public modulus" } {TEXT 361 6 ", and " }{TEXT 362 9 "calculate" }{TEXT 338 1 " " }{TEXT 317 4 "\nphi" }{TEXT 318 1 "(" }{TEXT 319 1 "n" }{TEXT 320 5 ") = (" } {TEXT 321 1 "p" }{TEXT 322 5 "-1)*(" }{TEXT 323 1 "q" }{TEXT 324 15 "- 1), the Euler " }{TEXT 325 3 "phi" }{TEXT 326 1 "-" }{TEXT 327 8 "func tion" }{TEXT 328 10 " value of " }{TEXT 329 1 "n" }{TEXT 330 0 "" }} {PARA 15 "" 0 "" {TEXT 303 6 "Choose" }{TEXT 339 1 " " }{TEXT 334 6 "p ublic" }{TEXT 333 1 " " }{TEXT 331 16 "encryption power" }{TEXT 332 1 " " }{TEXT 335 2 "e " }{TEXT 363 9 "such that" }{TEXT 364 1 " " } {TEXT 287 4 "gcd(" }{TEXT 340 1 "e" }{TEXT 341 2 ", " }{TEXT 342 3 "ph i" }{TEXT 343 1 "(" }{TEXT 344 1 "n" }{TEXT 345 7 ")) = 1 " }}{PARA 15 "" 0 "" {TEXT 288 9 "Calculate" }{TEXT 350 1 " " }{TEXT 348 26 "pri vate decryption power d" }{TEXT 349 11 " such that " }{TEXT 347 1 "e" }{TEXT 351 1 "*" }{TEXT 352 1 "d" }{TEXT 353 6 " = 1 (" }{TEXT 358 3 " mod" }{TEXT 359 1 " " }{TEXT 354 3 "phi" }{TEXT 355 1 "(" }{TEXT 356 1 "n" }{TEXT 357 2 "))" }{TEXT 346 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 290 16 "The central idea" } {TEXT -1 0 "" }{TEXT 291 2 " " }{TEXT -1 46 "The simple (but key) mat hematical point which " }}{PARA 0 "" 0 "" {TEXT -1 14 "allows one to \+ " }{TEXT 289 0 "" }{TEXT -1 14 "successfully '" }{TEXT 293 4 "sign" } {TEXT -1 37 "' (using RSA) is that the congruence:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 65 " \+ e*d = 1 (mod phi(n))," }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 7 "can be " }{TEXT 292 9 "rewritten" } {TEXT -1 4 " as:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 63 " d*e = 1 (mod p hi(n))" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 40 "The point is that one securely 'signs' (" }{TEXT 294 21 "explained in lectures" }{TEXT -1 16 ") by performing " }}{PARA 0 "" 0 "" {TEXT 365 26 "two successive encryptions" }{TEXT -1 1 ":" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 29 "1. using the other perso n's " }{TEXT 366 6 "public" }{TEXT -1 19 " key, together with" }} {PARA 0 "" 0 "" {TEXT -1 14 "2. one's own " }{TEXT 367 7 "private" } {TEXT -1 5 " key." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 4 "The " }{TEXT 295 5 "order" }{TEXT -1 41 " in which one per forms those encryptions " }{TEXT 296 7 "depends" }{TEXT -1 6 " upon " }}{PARA 0 "" 0 "" {TEXT -1 12 "who has the " }{TEXT 297 7 "smaller" } {TEXT -1 49 " public modulus (all this explained in lectures)." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 135 "`c rypt/alphabet` := `abcdefghijklmnopqrstuvwxyz`\n.`ABCDEFGHIJKLMNOPQRST UVWXYZ`\n.```1234567890-=~!@#$\243%^&*()_+`\n.` ,./<>?;':\"[]\{\}| \+ `:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 250 "to_number := proc(st , string) \nlocal ll, nn, ss, ii; \nll := length(st);\nif ll = 0 then RETURN(0) fi; \nnn := 1;\nfor ii to ll do \nss := SearchText(substrin g(st, ii .. ii),\n `crypt/alphabet`);\nnn := 100*nn + \+ ss \nod;\nnn - 10^(2*ll) \nend:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 272 "from_number := proc(nn, integer) \nlocal ss, mm, ll, pp, ii, \+ ans; mm := nn;\nll := floor(1/2*trunc(evalf(log10(mm))))+1;\nans := `` ; for ii to ll do mm := mm/100;\npp := 100*frac(mm);\nss := substring( `crypt/alphabet`, pp..pp);\nans := cat(ss, ans); mm := trunc(mm)\nod; \+ ans end:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 14 "I will create " }{TEXT 298 23 "public and private keys" }{TEXT -1 44 " for myself (John), and will use pj, qj, \+ etc" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 36 "Fi rst my two primes (note that I am " }{TEXT 299 3 "not" }{TEXT -1 12 " \+ exercising " }{TEXT 300 4 "care" }{TEXT -1 17 " with respect to " }} {PARA 0 "" 0 "" {TEXT -1 28 "their choice, meaning ... ):" }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 50 "pj := nextpr ime(10^49 + 654321); # 50 digit prime" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#pjG\"SjVl+++++++++++++++++++++5" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 56 "qj := nextprime(10^69 + 654321654321); # 70 digit pr ime" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#qjG\"ao^Wl@Vl+++++++++++++++ +++++++++++++5" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 9 "Next, my " } {TEXT 302 14 "public modulus" }{TEXT -1 1 ":" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "nj := pj*qj; " }} {PARA 12 "" 1 "" {XPPMATH 20 "6#>%#njG\"br8(>:x!)Q;G/+++++++++++++++^W l@Vl++++jVl+++++++++++++++++++++5" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 16 "Next, choose my " }{TEXT 301 23 "public encryption power" }{TEXT -1 1 ":" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "ej := nextprime(1234321); " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#ejG\"(LVB\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 " " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 46 "Now to calculate my PRIVATE decryption power, " } {TEXT 369 2 "dj" }{TEXT -1 1 "." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 56 "First, I must calculate the Euler phi-fun ction value of " }{TEXT 370 2 "nj" }}{PARA 0 "" 0 "" {TEXT -1 1 "(" } {TEXT 368 33 "bearing in mind the crucial point" }{TEXT -1 29 " that s omeone (else) who knew" }}{PARA 0 "" 0 "" {TEXT -1 13 "the value of " }{TEXT 371 2 "nj" }{TEXT -1 7 " would " }{TEXT 376 4 "only" }{TEXT -1 26 " be able to calculate the " }{TEXT 372 3 "phi" }{TEXT -1 10 "-valu e of " }{TEXT 373 2 "nj" }{TEXT -1 1 " " }}{PARA 0 "" 0 "" {TEXT -1 41 "- given current mathematical knowledge - " }{TEXT 374 2 "if" } {TEXT -1 19 " they could factor " }{TEXT 375 2 "nj" }{TEXT -1 2 ")." } }{PARA 0 "" 0 "" {TEXT -1 23 "Its value is given by: " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "phi_nj := (pj-1) *(qj-1);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%'phi_njG\"br+4@\\kAj\"G/ +++++++++++++++]Wl@Vl++++iVl+++++++++++++++++++++5" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 34 "Nex t I must test to see that 'gcd(" }{TEXT 378 2 "ej" }{TEXT -1 2 ", " } {TEXT 379 3 "phi" }{TEXT -1 1 "(" }{TEXT 380 2 "nj" }{TEXT -1 24 ")) = 1' is satisfied. I " }{TEXT 377 5 "could" }{TEXT -1 1 " " }}{PARA 0 " " 0 "" {TEXT -1 37 "do that by first calculating gcd(ej, " }{TEXT 257 3 "phi" }{TEXT -1 1 "(" }{TEXT 258 2 "nj" }{TEXT -1 29 ")), to see if \+ it came out to " }}{PARA 0 "" 0 "" {TEXT -1 56 "be 1 (and if it didn't then try some other value(s) for " }{TEXT 381 2 "ej" }{TEXT -1 18 "), and, if it did," }}{PARA 0 "" 0 "" {TEXT -1 67 "then go on to use the extended Euclidean algorithm to calculate the" }}{PARA 0 "" 0 "" {TEXT -1 17 "decryption power " }{TEXT 382 2 "dj" }{TEXT -1 30 " in th e usual way [recall the " }{TEXT 383 0 "" }{TEXT 384 5 "Maple" }{TEXT 385 0 "" }{TEXT -1 9 " command " }}{PARA 0 "" 0 "" {TEXT -1 12 "for th at is " }{TEXT 386 6 "igcdex" }{TEXT -1 57 " ... ]. However, it is sim plest to just go straight ahead" }}{PARA 0 "" 0 "" {TEXT -1 39 "and us e the igcdex command immediately:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "igcdex(ej, phi_nj, xj, yj); " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 36 "That '1' te lls us that the value of " }{TEXT 387 2 "ej" }{TEXT -1 33 " is o.k., a nd so I now proceed to" }}{PARA 0 "" 0 "" {TEXT -1 13 "calculate my " }{TEXT 388 22 "private decryption key" }{TEXT -1 1 " " }{TEXT 389 2 "d j" }{TEXT -1 1 ":" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 21 "dj := xj mod phi_nj; " }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%#djG\"ar(p\"=TY>+xy:&[EXdr/Cm%)[!zy61!yyjF68&\\]%4n9! 41)\\>85'=L\")=dwcMS+S\\$G)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 62 "The following calculation \+ isn't necessary; it is simply a case" }}{PARA 0 "" 0 "" {TEXT -1 62 "o f 'seeing is believing'. It is to see that the product of the" }} {PARA 0 "" 0 "" {TEXT -1 34 "encryption and decryption powers, " } {TEXT 391 2 "ej" }{TEXT -1 5 " and " }{TEXT 392 2 "dj" }{TEXT -1 10 ", really " }{TEXT 390 2 "is" }{TEXT -1 11 " congruent " }}{PARA 0 "" 0 "" {TEXT -1 16 "to 1 modulo the " }{TEXT 394 3 "phi" }{TEXT -1 19 "- function value of " }{TEXT 393 2 "nj" }{TEXT -1 1 ":" }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "ej*dj mod phi_nj; " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 395 51 "Making my \+ public keys known (to the world at large)" }{TEXT -1 15 ", I am now se t " }}{PARA 0 "" 0 "" {TEXT -1 6 "up to " }{TEXT 398 7 "receive" } {TEXT -1 52 " messages from anyone who knows my public keys, and " }} {PARA 0 "" 0 "" {TEXT -1 8 "also to " }{TEXT 399 4 "send" }{TEXT -1 56 " messages messages to anyone who knows my public keys. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 396 11 "For example" } {TEXT -1 60 ", let's say that you (Mary) wished to send me this messag e, " }}{PARA 0 "" 0 "" {TEXT 397 20 "using my public keys" }{TEXT -1 51 " (it being understood, of course, that we are also " }}{PARA 0 "" 0 "" {TEXT -1 36 "using the agreed 'crypt/alphabet'): " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 60 " \+ Meet at cinema, 9.30 P.M. Mary" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 27 "You - Mary - would do this:" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 401 5 "First" } {TEXT -1 53 " convert your message into numerical form, using the " }} {PARA 0 "" 0 "" {TEXT -1 20 "to_number procedure:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 52 "num1 := to_number(` Meet at cinema, 9.30 P.M. Mary`);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#> %%num1G\"gnD=,R!G)R#G/QmDG1==I^S\"4.!37+3_]!R" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 85 "[That in itial '39' is 'M', the following '05' is 'e', the next '05' is the oth er 'e'," }}{PARA 0 "" 0 "" {TEXT -1 67 "and so on, down to that final \+ '25', which is the 'y' at the end of " }{TEXT 400 4 "Mary" }{TEXT -1 2 ".]" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 406 4 " Next" }{TEXT -1 15 " you perform a " }{TEXT 408 17 "single encryption " }{TEXT -1 10 " using my " }{TEXT 402 6 "public" }{TEXT -1 11 " encry ption" }}{PARA 0 "" 0 "" {TEXT -1 6 "power " }{TEXT 403 2 "ej" }{TEXT -1 9 ", and my " }{TEXT 404 6 "public" }{TEXT -1 9 " modulus " }{TEXT 405 3 "nj:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 24 "enc1 := num1&^ej mod nj;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%%enc1G\"ar@@*)*e[c$4KTX[\"QwzY37Pm/g9M--(o&>`]&>Xhx2: nl\"*))oEZ6mnkyK]i?zs8wo" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 " " }}}{EXCHG {PARA 0 "" 0 "" {TEXT 407 23 "You send me that number" } {TEXT -1 46 " - enc1 - the encrypted form of the (ordinary)" }}{PARA 0 "" 0 "" {TEXT -1 65 "numerical form of the message, and then I proce ed to decrypt that" }}{PARA 0 "" 0 "" {TEXT -1 12 "by using my " } {TEXT 409 7 "private" }{TEXT -1 18 " decryption power " }{TEXT 410 2 " dj" }{TEXT -1 1 ":" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "dec1 := enc1&^dj mod nj;" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#>%%dec1G\"gnD=,R!G)R#G/QmDG1==I^S\"4.!37+3_]!R" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 4 "and " }{TEXT 411 4 "then" }{TEXT -1 8 " I just " }{TEXT 412 28 "recover the original message" }{TEXT -1 4 " by:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "text1 \+ := from_number(dec1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&text1G%?Me et~at~cinema,~9.30~P.M.~MaryG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 8 "Horray!!" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 4 "All " }{TEXT 413 5 "SEE MS" }{TEXT -1 51 " fine. You have sent me an encrypted message, and I " }}{PARA 0 "" 0 "" {TEXT -1 18 "have decrypted it." }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 4 "But " }{TEXT 421 3 "why " }{TEXT -1 2 " '" }{TEXT 414 5 "seems" }{TEXT -1 27 "'? [This brings us to the " }{TEXT 415 4 "crux" }{TEXT -1 17 " of the matter.] " }} {PARA 0 "" 0 "" {TEXT -1 59 "Well, you have used my public key to send me that message, " }}{PARA 0 "" 0 "" {TEXT 416 3 "BUT" }{TEXT -1 1 " \+ " }{TEXT 417 6 "anyone" }{TEXT -1 1 " " }{TEXT 418 5 "could" }{TEXT -1 46 " have sent me that message. Anyone, that is, " }}{PARA 0 "" 0 "" {TEXT -1 26 "who knows my public key. '" }{TEXT 419 3 "You" }{TEXT -1 2 "' " }{TEXT 420 21 "could be someone else" }{TEXT -1 6 " ... ." } }{PARA 0 "" 0 "" {TEXT -1 59 "[I'm not finished yet with the points I \+ wish to make ... .]" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT -1 60 "Equally I could send you a message. I could do it by u sing " }}{PARA 0 "" 0 "" {TEXT 422 15 "your public key" }{TEXT -1 32 " (if you had one which I knew), " }{TEXT 423 3 "BUT" }{TEXT -1 10 " 'I ' also " }}{PARA 0 "" 0 "" {TEXT -1 65 "could be someone else ... . [I 'm not yet finished with the points" }}{PARA 0 "" 0 "" {TEXT -1 21 "I \+ wish to make ... .]" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT -1 2 "I " }{TEXT 424 5 "could" }{TEXT -1 33 " send you a messa ge using my own " }{TEXT 425 7 "private" }{TEXT -1 6 " key (" }{TEXT 426 8 "assuming" }{TEXT -1 1 " " }}{PARA 0 "" 0 "" {TEXT -1 45 "you kn ow my public key), and I could do that " }{TEXT 427 3 "NOT" }{TEXT -1 15 " by encrypting " }}{PARA 0 "" 0 "" {TEXT -1 61 "using my public en cryption power (which anyway would require " }}{PARA 0 "" 0 "" {TEXT -1 44 "that you knew my private decryption power), " }{TEXT 428 3 "BUT " }{TEXT -1 15 " by encrypting " }}{PARA 0 "" 0 "" {TEXT -1 13 "using \+ my own " }{TEXT 429 7 "private" }{TEXT -1 31 " decryption power to enc rypt. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 430 11 "For example" }{TEXT -1 48 ", suppose I want to send you (Mary) the message:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 52 " Can't make it. Too much work. John" }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 256 5 "First" }{TEXT -1 51 " convert my message into numerical form, using the " }}{PARA 0 "" 0 "" {TEXT -1 20 "to_number procedure:" }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 56 "num2 := to_number(`Can't make i t. Too much work. John`);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%%num2G \"_o93:O!G=\"=:B!)3.@8!e^h/G3#4!e56I,3#)[6!H" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 260 4 "Next" }{TEXT -1 13 " I perform a " }{TEXT 261 17 "single encryp tion" }{TEXT -1 3 ", " }{TEXT 431 3 "BUT" }{TEXT -1 10 " using my " } {TEXT 256 7 "private" }{TEXT -1 11 " decryption" }}{PARA 0 "" 0 "" {TEXT -1 6 "power " }{TEXT 257 2 "dj" }{TEXT -1 9 ", and my " }{TEXT 258 6 "public" }{TEXT -1 9 " modulus " }{TEXT 259 3 "nj:" }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "enc2 := num2&^dj mod nj; " }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%%enc2G\"ar( eg6_;0I&*\\BXH4OlO(p2LmA7?W^M@v7!Q#)f\"3o9-$fw')RTWf%plzf5%Q" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 " " {TEXT -1 0 "" }{TEXT 256 22 "I send you that number" }{TEXT -1 46 " \+ - enc2 - the encrypted form of the (ordinary)" }}{PARA 0 "" 0 "" {TEXT -1 40 "numerical form of the message, and then " }{TEXT 432 3 "y ou" }{TEXT -1 25 " then proceed to decrypt " }}{PARA 0 "" 0 "" {TEXT -1 17 "that by using my " }{TEXT 257 6 "public" }{TEXT -1 18 " decrypt ion power " }{TEXT 258 2 "ej" }{TEXT -1 1 ":" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "dec2 := enc2&^ej \+ mod nj;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%%dec2G\"_o93:O!G=\"=:B!)3 .@8!e^h/G3#4!e56I,3#)[6!H" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 4 "and " }{TEXT 256 4 "then" } {TEXT -1 10 " you just " }{TEXT 257 28 "recover the original message" }{TEXT -1 4 " by:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 27 "text2 := from_number(dec2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&text2G%CCan't~make~it.~Too~much~work.~JohnG" }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 8 "Horray!!" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT -1 16 "Once again, all " }{TEXT 433 5 "SEEMS" }{TEXT -1 6 " fi ne." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 9 "But why '" }{TEXT 434 5 "seems" }{TEXT -1 23 "'? Well, at least you " } {TEXT 435 4 "know" }{TEXT -1 22 " the message has come " }}{PARA 0 "" 0 "" {TEXT -1 62 "from me (since - in theory - ONLY I know MY private \+ key), BUT " }}{PARA 0 "" 0 "" {TEXT -1 38 "ANYONE could also read that message. " }{TEXT 437 6 "Anyone" }{TEXT -1 11 ", that is, " }{TEXT 438 3 "who" }{TEXT -1 7 " (like " }}{PARA 0 "" 0 "" {TEXT -1 5 "you) \+ " }{TEXT 436 19 "knows my public key" }{TEXT -1 1 "." }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 439 9 "Of course" }{TEXT -1 2 ", " }{TEXT 440 2 "if" }{TEXT -1 38 " you had your public and private \+ keys " }{TEXT 441 4 "then" }{TEXT -1 14 " that problem " }}{PARA 0 "" 0 "" {TEXT -1 64 "could be avoided by my sending you the above message using your " }}{PARA 0 "" 0 "" {TEXT -1 29 "public encryption power . .. ." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 442 3 "B UT" }{TEXT -1 55 " then you couldn't be sure the message is from me .. . ." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 44 "[I hope you see what the problems are ... .]" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 73 "While we are at it - and before making progress - I would like to divert " }}{PARA 0 "" 0 "" {TEXT -1 67 "briefly to illustrate what happens if someone ATTEMPTS to GUESS my " }}{PARA 0 "" 0 "" {TEXT -1 62 "private decryption power, in an a ttempt to FORGE my signature:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 59 "Suppose they wished to send the same mess age as above, and " }}{PARA 0 "" 0 "" {TEXT -1 29 "went through the us ual steps:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 56 "NUM2 := to_number(`Can't make it. Too much work. John `);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%%NUM2G\"_o93:O!G=\"=:B!)3.@8! e^h/G3#4!e56I,3#)[6!H" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" } }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 36 "Let's say they choose the follow ing " }{TEXT 444 6 "forged" }{TEXT -1 14 " value for my " }{TEXT 445 7 "private" }{TEXT -1 1 " " }}{PARA 0 "" 0 "" {TEXT -1 17 "decryption \+ power:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "DJ_guess := 10^26 + 9876548765432;" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#>%)DJ_guessG\" " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 18 "and n ow encrypted:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "ENC2 := NUM2&^DJ_guess mod nj; " }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%%ENC2G\"ar]([exuMi'\\gn:N\"[zAd;-W=*4')pIIi8%*\\ %=-C3Q_>cG2&f@S``\"*)=c\"*f:$G(Hs8&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 63 "They send you that number, and you now proceed to (attempt to) " }}{PARA 0 "" 0 "" {TEXT -1 21 "decrypt it, using my " }{TEXT 443 7 "genuine" }{TEXT -1 1 " " }{TEXT 446 6 "public" }{TEXT -1 5 " key:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "DEC2 := ENC 2&^ej mod nj; " }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%%DEC2G\"ar;Mg\"=Zw ce]i:M@#fj-$*fvKlcqU%Q]QxAo]>K-mw=Z,rlDK.PPHa?!>!=up@dy)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 63 "There is nothing apparently untoward there, but now the game is " }}{PARA 0 "" 0 "" {TEXT -1 49 "up when you attempt to recover the or iginal text:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "text2 := from_number(DEC2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&text2G%fn;>%p~O~sbeP|fr^$Gv34jn|^u;|ir7wu|grf.A^>c

!-|^u,7HpG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 447 41 "The forger would have w asted his/her time" }{TEXT -1 14 ". The message " }}{PARA 0 "" 0 "" {TEXT -1 25 "decrypts as gobbledegook." }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT 448 19 "COMING TO THE POINT" }{TEXT -1 14 ". One of the " }{TEXT 449 5 "MAJOR" }{TEXT -1 14 " applications " }} {PARA 0 "" 0 "" {TEXT -1 45 "of public-key cryptography is that it all ows " }{TEXT 450 6 "SECURE" }{TEXT -1 7 " 2-way " }}{PARA 0 "" 0 "" {TEXT -1 1 "'" }{TEXT 451 6 "signed" }{TEXT -1 50 "' communication bet ween two parties who each have " }}{PARA 0 "" 0 "" {TEXT -1 62 "their \+ own public and private keys (with, of course, an agreed " }}{PARA 0 " " 0 "" {TEXT -1 62 "system for converting text into numerical form). [ That is what" }}{PARA 0 "" 0 "" {TEXT -1 64 "President Clinton and Mr. Ahern were doing in a very public way," }}{PARA 0 "" 0 "" {TEXT -1 65 "but it is exactly what everyone else is doing all the time ... .] " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 58 "Let u s have parties A and B with public and private keys (" }{TEXT 453 2 "e a" }{TEXT -1 2 ", " }{TEXT 454 2 "na" }{TEXT -1 2 ", " }{TEXT 455 2 "d a" }{TEXT -1 2 ") " }}{PARA 0 "" 0 "" {TEXT -1 5 "and (" }{TEXT 456 2 "eb" }{TEXT -1 2 ", " }{TEXT 457 2 "nb" }{TEXT -1 2 ", " }{TEXT 458 2 "db" }{TEXT -1 52 "); then these parties can communicate securely with " }}{PARA 0 "" 0 "" {TEXT -1 68 "each other [IMPLICIT in ALL of this \+ - of course - is the ASSUMPTION " }}{PARA 0 "" 0 "" {TEXT -1 5 "that \+ " }{TEXT 452 2 "na" }{TEXT -1 39 " and nb have been created so that th ey " }{TEXT 459 6 "cannot" }{TEXT -1 13 " be factored " }}{PARA 0 "" 0 "" {TEXT -1 13 "QUICKLY!!]. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT 460 22 "This is how it is done" }{TEXT -1 1 ":" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 461 5 "First" }{TEXT -1 50 " let's create public and private keys for A and B " }} {PARA 0 "" 0 "" {TEXT -1 57 "[I am not going to be fussy about the cho ice of primes. " }}{PARA 0 "" 0 "" {TEXT -1 39 "I am merely choosing \+ them to be 'big']:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 27 "I make up the first prime, " }{TEXT 462 2 "pa" }{TEXT -1 38 ", so that it has 100 digits [that can " }}{PARA 0 "" 0 "" {TEXT -1 54 "take a while, depending on the speed of the computer]:" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 57 "pa \+ := nextprime(10^99 + 8765432109876543211234567834567);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%#paG\"_q4^$ycM7@Vl()4@Vl(3++++++++++++++++++++++ +++++++++++5" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 22 "and the second prime, " }{TEXT 463 2 "qa " }{TEXT -1 50 ", so that it has 120 digits [here too, time ... ]:" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 58 "qa := nextprime(10^119 + 8765432109876543211234567834567);" }} {PARA 12 "" 1 "" {XPPMATH 20 "6#>%#qaG\"crF_$ycM7@Vl()4@Vl(3++++++++++ +++++++++++++++++++++++++++++++++5" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 31 "Now to form A 's public modulus:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "na := pa*qa;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%#naG\"fxVZeep(*\\lU@=Sn)G78**yuaG2+G$o2+++++++++++++++++ +F_$ycM7@Vlx?c@AA8@Vl()4@Vl(3+++++++++++++++++++++++++++++++++5" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 58 "Now to choose A's public encryption power, followed by th e" }}{PARA 0 "" 0 "" {TEXT -1 28 "other standard computations:" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "ea := nextprime(12321);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#ea G\"&BB\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "phi_na := (pa - 1)*(qa - 1);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%'phi_naG\"fx3W\">)G $*o<(QAIBc!H%Qn)G78**yuaG2+G$o2++++++++++++++++++E_$ycM7@Vln?c@AA8@Vl( )4@Vl(3+++++++++++++++++++++++++++++++++5" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 27 "igcdex(ea, phi_na, xa, ya);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "da := xa mod phi_na;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%#daG\"exNi6jcV /M8mWx[o/\\.ob3D44!=+-?2+!)zl(oiDa=02(pqcW'f]b?*G&y:)4Kw.!R8cq*o0(eWG1 <&*=8m#**\\]*pgS_aZn&4F2[7%z=3 \+ " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 54 "Checki ng (unneccessarily) that ea*da = 1 (mod phi_na):" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "ea*da mod phi_na;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 54 "Now to do mak e similar choices and calculations for B:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 74 "pb := nextprime(10^109 + 222 8765432109876543211234567834000); # 110 digits" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%#pbG\"iqtT$ycM7@Vl()4@Vl(GA++++++++++++++++++++++++++ +++++++++++5" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 74 "qb := nextp rime(10^129 + 2228765432109876543211234567834000); # 130 digits" }} {PARA 12 "" 1 "" {XPPMATH 20 "6#>%#qbG\"]sxS$ycM7@Vl()4@Vl(GA+++++++++ ++++++++++++++++++++++++++++++++++++++5" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "nb := pb*qb;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%#nb G\"jy@L^9N4c&>y]Z`/Ir6kBT71y0mqCzO^`Rn\\+++++++++++++++++++++xS$ycM7@V l " 0 "" {MPLTEXT 1 0 23 "eb := nextprime(54321);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#ebG\"&BV&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "phi_nb := (pb - 1)*(qb - 1);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%'phi_nbG\"jys]%)yViLJtax7\"=*ff'fBT71y0mqCzO^`Rn\\+++ ++++++++++++++++++wS$ycM7@Vl2Fb@AANBVl()4@Vl(GA+++++++++++++++++++++++ ++++++++++++++5" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "igcdex(e b, phi_nb, xb, yb);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "db := xb mod phi_nb;" }} {PARA 12 "" 1 "" {XPPMATH 20 "6#>%#dbG\"iyjz$H_C@;_G7$>db+99<'=.Ctstqw C1D?+/B$)3[*R8F?c.bhoi*[uX]IB!Qrw?(pxA7l'=T^'*\\*pXQX(Q![&yQ_-(p)ocNtP u_wOOG/^ks>3*oHkk3h#zTRph#3W6&z4t" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 54 "Checking (unn eccessarily) that eb*db = 1 (mod phi_nb):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "eb*db mod phi_nb;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6# \"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 464 40 "So, A and B have public and private keys" } {TEXT -1 25 ", and we are in business." }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 30 "Let B send a 'signed' message:" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 3 " " } {TEXT 465 62 "If we give you \2431,000,000 will we get the government \+ contract?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 6 "to A. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 466 12 "KEEP IN MIND" }{TEXT -1 28 " that A's public modulus is " } {TEXT 467 4 "LESS" }{TEXT -1 21 " than B's (na < nb), " }}{PARA 0 "" 0 "" {TEXT -1 29 "and that one always uses the " }{TEXT 468 7 "SMALLER " }{TEXT -1 9 " modulus " }{TEXT 469 5 "FIRST" }{TEXT -1 3 ". " }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 17 "Recall th e steps:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 86 "B_num := to_number(`If we give you \2431,000,000 will we get the government contract?`); " }}{PARA 12 "" 1 "" {XPPMATH 20 " 6#>%&B_numG\"gr'3K5!=?9:.!3U^IT\"=0A:2!e!3?!3_q+eI-G@\"4B!QOO;QOO;[:2= _^-e?#42!eI-o]$" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "length(B _num);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"$C\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 62 "Becau se length(B_num) < na, then the message can be sent as a " }}{PARA 0 " " 0 "" {TEXT 470 12 "single block" }{TEXT -1 52 " (I could have made a much longer message, as there " }}{PARA 0 "" 0 "" {TEXT -1 25 "is qui te a bit to spare)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT 471 13 "B now does a " }{TEXT 472 17 "double encryption" } {TEXT -1 1 ":" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 38 "FIRST using A's smaller modulus, with " }}{PARA 0 "" 0 " " {TEXT -1 41 " A's PUBLIC encryption power," }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 35 "SECOND using B's o wn modulus, with " }}{PARA 0 "" 0 "" {TEXT -1 42 " B's PRI VATE decryption power:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 53 "B_first := B_num&^ea mod na; # SMALLER modulu s FIRST" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%(B_firstG\"ex3Eo-V9`,)*)= *pLs/[dr#p]'[AJ5:j$Rhc4r#=3!Q)>T(G9:r:zKIx77!)*GbAXbej0#e'zwm*zuc5I^?c wI22e#e(*3;^Tul^^H'G*)e%o&z\\A.we&RS8#HIA(" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 31 "B_second := B_first&^db mod nb;" }}{PARA 12 "" 1 " " {XPPMATH 20 "6#>%)B_secondG\"iyQ/$)zeq]u%))4ku!eC;$*))=kaKp$*Rhig#=/ CY'pipc-\\SE\\Fi(oh)*y/g4B%>OxcAW3%p4#>,bCb1X:$fh/$o1C\"=#4\"Qkx(4FV]? ]p**ef#[cv-Mr^vp$etk-Km`egK:hGa" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 58 "B_second is what A rec eives, and A now proceeds to do the " }}{PARA 0 "" 0 "" {TEXT 473 17 " double decryption" }{TEXT -1 20 " as follows (simply " }{TEXT 474 9 "r eversing" }{TEXT -1 21 " the last two steps):" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 52 "FIRST using B's modulus, \+ with B's PUBLIC encryption " }}{PARA 0 "" 0 "" {TEXT -1 7 "power, " }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 47 "SECOND us ing A's own modulus, with A's PRIVATE " }}{PARA 0 "" 0 "" {TEXT -1 17 "decryption power:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 " " {MPLTEXT 1 0 31 "A_first := B_second&^eb mod nb;" }}{PARA 12 "" 1 " " {XPPMATH 20 "6#>%(A_firstG\"ex3Eo-V9`,)*)=*pLs/[dr#p]'[AJ5:j$Rhc4r#= 3!Q)>T(G9:r:zKIx77!)*GbAXbej0#e'zwm*zuc5I^?cwI22e#e(*3;^Tul^^H'G*)e%o& z\\A.we&RS8#HIA(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "A_secon d := A_first&^da mod na;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%)A_secon dG\"gr'3K5!=?9:.!3U^IT\"=0A:2!e!3?!3_q+eI-G@\"4B!QOO;QOO;[:2=_^-e?#42! eI-o]$" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "from_number(A_sec ond);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%inIf~we~give~you~|^u1,000,00 0~will~we~get~the~government~contract?G" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 475 32 "Now let A re ply with the message" }{TEXT -1 2 ": " }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 258 "" 0 "" {TEXT -1 107 " You're joking! \2432,000,000 a nd it's yours. You'll recoup \n all with contract. Leave cash usual place." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 121 "A_num := to_number(`You're joking! \2432,000,000 and it's you rs.You'll recoup all with contract. Leave cash usual place.`);" }} {PARA 12 "" 1 "" {XPPMATH 20 "6#>%&A_numG\"_w#eI5?h,G65#>@!)3>,.!e?7]! Q!3G3K5!=?9:.!)3?4B!G@6+o6_J]!=!G@\")=_6D)>=@:D!)>)3#4![S6+QOO;QOO;e:2 ywS\"46:5!e!=)=_6&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "lengt h(A_num);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"$'>" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "length(na);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"$>#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 47 "Again, because length(A_num) < na, the me ssage " }}{PARA 0 "" 0 "" {TEXT -1 17 "can be sent as a " }{TEXT 476 12 "single block" }{TEXT -1 1 "." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 53 "A_first := A_num&^da mod na; # SMA LLER modulus first" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%(A_firstG\"exB V2?#4,%>My<;)pO&*3zl,63j#HJ!*f3#Qz79Y%Gq5!z$f<**\\@7*p,A;%z]`#)4\\@'Ry #Rqe0MG'ecK'eGC0B$=*eW<'\\V[H(3L3ASdDUJ&QXf[t+(=*e$>0C:V" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "A_second := A_first&^eb mod nb;" }} {PARA 12 "" 1 "" {XPPMATH 20 "6#>%)A_secondG\"iy8lo'R6!)[&4ucpZ$zW,\"Q hIFNxJaj])y*)f#)QFm^51rbX^1tPI@O2T)\\SX$\\K(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 51 "A_second is what B receives, and B now proceeds to " }}{PARA 0 "" 0 "" {TEXT -1 53 "decrypt A's message as follows (simply reversing the " }}{PARA 0 "" 0 "" {TEXT -1 16 "last two steps):" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "B_first := A_second&^db mod nb ;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%(B_firstG\"exBV2?#4,%>My<;)pO&* 3zl,63j#HJ!*f3#Qz79Y%Gq5!z$f<**\\@7*p,A;%z]`#)4\\@'Ry#Rqe0MG'ecK'eGC0B $=*eW<'\\V[H(3L3ASdDUJ&QXf[t+(=*e$>0C:V" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "B_second := B_first&^ea mod na;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%)B_secondG\"_w#eI5?h,G65#>@!)3>,.!e?7]!Q!3G3K5!=?9:.! )3?4B!G@6+o6_J]!=!G@\")=_6D)>=@:D!)>)3#4![S6+QOO;QOO;e:2ywS\"46:5!e!=) =_6&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "from_number(B_secon d);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%]qYou're~joking!~|^u2,000,000~ and~it's~yours.You'll~recoup~all~with~contract.~~Leave~cash~usual~plac e.G" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 " " 0 "" {TEXT -1 17 "Now you know the " }{TEXT 479 10 "essentials" } {TEXT -1 4 " of " }{TEXT 477 18 "digital signatures" }{TEXT 478 1 "." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 259 "" 0 "" {TEXT -1 48 "##### ##########################\n#\n# " }{TEXT 480 165 "John B. Cosgrave\n# Mathematics Department,\n# St. Pa trick's College,\n# Drumcondra,\n# Dublin 9,\n # IRELAND.\n" }{TEXT -1 528 "#\n# [St. Patrick' s College is a \n# College of Dublin City University]\n#\n # Home e-mail: johnbcos@iol.ie\n# Colleg e e-mail: John.Cosgrave@spd.ie\n#\n# Is 2^p - 1 prime for infi nitely many p? (I hope so.)\n# Is 2^(2^n) + 1 prime for some n > 4? (Surely at least one?)\n# Is Pi^e transcendental? (Probably. )\n# Is 2^sqrt(2) + 3^sqrt(3) irrational? (Almost certainly.)\n# Is zeta(3) a rational multiple of Pi^3? (Hardly.)\n#\n######### ######################" }}}}{MARK "106 2 0" 1 }{VIEWOPTS 1 1 0 1 1 1803 }