WOW! eBook www.wowebook.org HOW SOFTWARE WORKS The Magic Behind Encryption, CGI, Search Engines, and Other Everyday Technologies by V. Anton Spraul San Francisco WOW! eBook www.wowebook.org HOW SOFTWARE WORKS. Copyright © 2015 by V. Anton Spraul. All rights reserved. No part of this work may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, recording, or by any information storage or retrieval system, without the prior written permission of the copyright owner and the publisher. Printed in USA First printing 19 18 17 16 15 1 2 3 4 5 6 7 8 9 ISBN-10: 1-59327-666-4 ISBN-13: 978-1-59327-666-9 Publisher: William Pollock Production Editor: Alison Law Cover Illustration: Josh Ellingson Interior Design: Octopod Studios Developmental Editors: Hayley Baker, Seph Kramer, and Greg Poulos Technical Reviewer: Randall Hyde Copyeditor: Rachel Monaghan Compositor: Susan Glinert Stevens Proofreader: James Fraleigh For information on distribution, translations, or bulk sales, please contact No Starch Press, Inc. directly: No Starch Press, Inc. 245 8th Street, San Francisco, CA 94103 phone: 415.863.9900; [email protected] www.nostarch.com Library of Congress Cataloging-in-Publication Data: Spraul, V. Anton. How software works : the magic behind encryption, CGI, search engines, and other everyday technologies / by V. Anton Spraul. pages cm Includes index. Summary: “A guide for non-technical readers that explores topics like data encryption; computer graphics creation; password protection; video compression; how data is found in huge databases; how programs can work together on the same problem without conflict; and how map software finds routes.”— Provided by publisher. ISBN 978-1-59327-666-9 — ISBN 1-59327-666-4 1. Electronic data processing—Popular works. 2. Computer software—Popular works. 3. Computer networks— Popular works. I. Title. QA76.5.S6663 2015 005.3—dc23 2015022623 No Starch Press and the No Starch Press logo are registered trademarks of No Starch Press, Inc. Other product and company names mentioned herein may be the trademarks of their respective owners. Rather than use a trademark symbol with every occurrence of a trademarked name, we are using the names only in an editorial fashion and to the benefit of the trademark owner, with no intention of infringement of the trademark. The information in this book is distributed on an “As Is” basis, without warranty. While every precaution has been taken in the preparation of this work, neither the author nor No Starch Press, Inc. shall have any liability to any person or entity with respect to any loss or damage caused or alleged to be caused directly or indirectly by the information contained in it. WOW! eBook www.wowebook.org About the Author V. Anton Spraul has taught introductory programming and computer science to students from all over the world for more than 15 years. He is also the author of Think Like a Programmer (No Starch Press) and Computer Science Made Simple (Broadway). WOW! eBook www.wowebook.org About the Technical Reviewer Randall Hyde is the author of The Art of Assembly Language and Write Great Code (both No Starch Press), and is also the co-author of The Waite Group’s Microsoft Macro Assembler 6.0 Bible (Sams Publishing). Hyde taught assembly language at the University of California, Riverside, for more than a decade and has been programming software for nuclear reactor consoles for the past 12 years. WOW! eBook www.wowebook.org Brief Contents Acknowledgments Introduction Chapter 1: Encryption Chapter 2: Passwords Chapter 3: Web Security Chapter 4: Movie CGI Chapter 5: Game Graphics Chapter 6: Data Compression Chapter 7: Search Chapter 8: Concurrency Chapter 9: Map Routes Index WOW! eBook www.wowebook.org Contents in Detail Acknowledgments Introduction Who This Book Is For Topics Covered Behind the Magic 1 Encryption The Goal of Encryption Transposition: Same Data, Different Order Cipher Keys Attacking the Encryption Substitution: Replacing Data Varying the Substitution Pattern Key Expansion The Advanced Encryption Standard Binary Basics AES Encryption: The Big Picture Key Expansion in AES AES Encryption Rounds Block Chaining Why AES Is Secure Possible AES Attacks The Limits of Private-Key Encryption 2 Passwords Transforming a Password into a Number Properties of Good Hash Functions The MD5 Hash Function Encoding the Password Bitwise Operations MD5 Hashing Rounds Meeting the Criteria of a Good Hash Function WOW! eBook www.wowebook.org Digital Signatures The Problem of Identity Collision Attacks Passwords in Authentication Systems The Dangers of Password Tables Hashing Passwords Dictionary Attacks Hash Tables Hash Chaining Iterative Hashing Salting Passwords Are Password Tables Safe? Password Storage Services A Final Thought 3 Web Security How Public-Key Cryptography Solves the Shared Key Problem Math Tools for Public-Key Cryptography Invertible Functions One-Way Functions Trapdoor Functions The RSA Encryption Method Creating the Keys Encrypting Data with RSA RSA Effectiveness RSA Use in the Real World RSA for Authentication Security on the Web: HTTPS Handshaking Transmitting Data Under HTTPS The Shared Key Problem Solved? 4 Movie CGI Software for Traditional Animation WOW! eBook www.wowebook.org How Digital Images Work How Colors Are Defined How Software Makes Cel Animations From Cel Animation Software to Rendered 2D Graphics Software for 3D CGI How 3D Scenes Are Described The Virtual Camera Direct Lighting Global Illumination How Light Is Traced Full-Scene Anti-Aliasing Combining the Real and the Fake The Ideal of Movie-Quality Rendering 5 Game Graphics Hardware for Real-Time Graphics Why Games Don’t Ray Trace All Lines and No Curves Projection Without Ray Tracing Rendering Triangles The Painter’s Algorithm Depth Buffering Real-Time Lighting Shadows Ambient Light and Ambient Occlusion Texture Mapping Nearest-Neighbor Sampling Bilinear Filtering Mipmaps Trilinear Filtering Reflections Faking Curves Distant Impostors WOW! eBook www.wowebook.org Bump Mapping Tessellation Anti-Aliasing in Real Time Supersampling Multisampling Post-Process Anti-Aliasing The Rendering Budget What’s Next for Game Graphics 6 Data Compression Run-Length Encoding Dictionary Compression The Basic Method Huffman Encoding Reorganizing Data for Better Compression Predictive Encoding Quantization JPEG Images A Different Way to Store Colors The Discrete Cosine Transform The DCT for Two Dimensions Compressing the Results JPEG Picture Quality Compressing High-Definition Video Temporal Redundancy MPEG-2 Video Compression Video Quality with Temporal Compression The Present and Future of Video Compression 7 Search Defining the Search Problem Putting Data in Order Selection Sort Quicksort WOW! eBook www.wowebook.org