APPENDIX CSAGE EXERCISESBy Dan ShumowUniversity of WashingtonC.1 Getting Started With Sage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . C-2C.2 Programming With Sage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . C-4Input to the Interpreter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . C-4Data Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . C-4Mathematical Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . C-6Control Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . C-6Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . C-7C.3 Chapter 2: Classical Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . C-8C.4 Chapter 3: Block Ciphers And The Data Encryption Standard . . . . . . . . C-9C.5 Chapter 4: Basic Concepts In Number Theory And Finite Fields . . . . . C-10C.6 Chapter 5: Advanced Encryption Standard . . . . . . . . . . . . . . . . . . . . . . . . C-12C.7 Chapter 6: Pseudorandom Number Generation And Stream Ciphers . . C-13C.8 Chapter 8: Number Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . C-14C.9 Chapter 9: Public-Key Cryptography And RSA . . . . . . . . . . . . . . . . . . . . C-18C.10 Chapter 10: Other Public-Key Cryptosystems . . . . . . . . . . . . . . . . . . . . . . C-19C.11 Chapter 11: Cryptographic Hash Functions . . . . . . . . . . . . . . . . . . . . . . . . C-22C.12 Chapter 13: Digital Signatures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . C-22C-1Z03_STAL7044_05_SE_APPC.QXD 12/4/09 1:54 PM Page C-1C-2 APPENDIX C / SAGE EXERCISESThis appendix contains a number of exercises that reinforce cryptographic concepts,organized by the chapter in which those concepts were discussed. All the exercisesuse Sage. We begin with a discussion of how to get started using Sage and a briefintroduction to the syntax and operations.C.1 GETTING STARTED WITH SAGESage is a free open source program that collects many open source math packagesinto one easily usable environment.The following are step-by-step instructions to installing and getting startedusing Sage for the examples and exercises in this book.11. Go to http://www.sagemath.org/download/2. You have two options:a. Building from source: If you are well versed in compilers and building soft-ware, you can build from source. Select this option.b. Installing Binaries: You can install precompiled binaries, the process is dif-ferent on several different operating systems.• Linux Download the Linux binaries, download, and follow the instructionsin the README file.• Mac OS X Download the Mac OS X binaries and follow the instructions inthe README file.• Windows: With Windows the process is a little bit more complicated. At thetime of printing the only complete option for Sage on Windows requiresrunning ubuntu in a virtual machine. The directions are contained in thewindows section of the download. However, copied here for reference theyare:i) Download the VMWare player: http://www.vmware.com/products/player/(this is a free download for students / educators.)ii) Download the VMWare image from the Sage website and follow thedirections in the README file.There is also a native port of windows, in progress, at the time of thisprinting. You can try it and see if it works for your purposes at:http://windows.sagemath.com3. Once you have Sage installed, On Linux or Mac OS X you can just type Sagefrom a shell prompt and it will run the interpreter (if you installed theSage script in the correct location, as in the README files.) On windows, yourun Sage by starting the VMWare player to open the Sage virtual hard drive.Once the VMWare player is started, you can use the player to enter data intothe command line, you can SSH to your virtual machine (useful for copy andpaste functionality) and use the notebook.4. Sage also has notebook functionality, similar to that of Maple or Mathemati-ca worksheets. This runs through the web browser. On Linux and Mac OS X,1Please note that Sage is an open source package that is constantly under development, and much func-tionality changes from release to release. If any of the steps in this section do not work, please checkhttp://www.sagemath.org for new up-to-date information.Z03_STAL7044_05_SE_APPC.QXD 12/4/09 1:54 PM Page C-2C.1 / GETTING STARTED WITH SAGE C-3you start the notebook by typing notebook() from the command prompt, orby running Sage with the -notebook argument. In the VMWare image, this isrun by selecting notebook from the login options when the VMWare imagestarts up.5. If you wish to execute the Sage examples from Appendix B, you can nowdownload the relevant Sage files.2If you are using a Linux or Mac OS Xmachine, then you just download your files to a folder and run Sage to accessthem. However, if you are using the VMWare player then you need to get thefiles into your virtual machine. This can be done using the shared folder’soption in VMWare player, or copying the files using wget or scp from insidethe virtual machine. You can access the underlying Ubuntu operating systemin the Sage virtual machine by selecting the manage option when the VMWareimage starts up.6. As mentioned in step 3, Sage is an interpreted language, and you interact withit through a prompt. However you can also write batch scripts.These files havethe suffix .sage and each line is a line that you would type into the …