Public Keys, One Way Functions and Hard Problems

832 Download(s)

Lesson synopsis

Public KeySecurity has always been a major focus of computer science research, and with the explosion of Internet use by commerce, the need for secure transactions has taken on more urgency. Most recently, cyber-thieves demonstrated that true security on the Internet is going to require a new level of understanding of how to protect personal data, and more importantly, financial transactions. This lesson introduces two important concepts: public key encryption and one-way functions. It provides an opportunity for students to understand the underpinnings of almost all Internet security: they will come to appreciate that any lock can be eventually broken, and that theoretical computer scientists study ‘hard’ problems to lengthen the time it will take to break a lock. Note that this is not a lesson in encryption, but in how mathematics is used to secure information.

Age Levels

11 - 14 years

Objectives

Introduce students to:
The concept of a public key
How the modulo function is a one-way function
How the Diffie-Hellman key exchange uses a one-way function
What computer scientists mean by ‘hard’ problems

Anticipated learner outcomes

Students will be able to
Practice creating public keys with the classic color model.
Exchange information with the Diffie-Hellman method using modulo arithmetic.
Explain why no lock can be completely secured, and that given time, any mathematical ‘lock’ can be broken.
Use exponentiation and modulo arithmetic to create cyber-keys.
Router
Sandra Lerner

It is difficult to imagine a time when computers were not capable of sharing information and resources with great ease. Sandra Lerner pushed the boundaries of network computing as one of the co-founders of Cisco Systems, which introduced one of the first commercially viable routers. The router was born while Sandra was working at Stanford University in the 1980’s after earning her Master’s degree there in Computer Science. To avoid the tedious task of transferring information between computers using floppy disks, she and co-founder of Cisco, Leonard Bosack, created a local area network, or LAN, between their campus offices using a multiprotocol router that Bosack developed. Shortly thereafter the pair started Cisco Systems, and began selling the router which was a success, because it could work with so many different types of computers. After Leaving Cisco in 1990, Lerner started the trendy cosmetics company Urban Decay and became a philanthropist and avid activist for animal rights.

MATLAB graph
Cleve Moler

Cleve Moler improved the quality and accessibility of mathematical software and created a highly respected software system called MATLAB. He was a professor of mathematics and computer science for almost 20 years at the University of Michigan, Stanford University, and the University of New Mexico. In the late 1970’s to early 1980’s he developed several mathematical software packages to support computational science and engineering. These packages eventually formed the basis of MATLAB, a programming environment for algorithm development, data analysis, visualization, and numerical computation. MATLAB can be used to solve technical computing problems faster than with traditional programming languages, such as C, C++, and Fortran. Today, Professor Moler spends his time writing books, articles, and MATLAB programs.

Listen to what Professor Moler has to say about his life’s work: http://www.youtube.com/watch?v=IT5umwNSAxE

First computer mouse
Douglas Engelbart
Douglas Engelbart

In 1967, Douglas Engelbart applied for a patent for an "X-Y position indicator for a display system," which he and his team developed at the Stanford Research Institute (SRI) in Menlo Park, California. The device, a small, wooden box with two metal wheels, was nicknamed a "mouse" because a cable trailing out of the one end resembled a tail.

In addition to the first computer mouse, Engelbart’s team developed computer interface concepts that led to the GUI interface, and were integral to the development of ARPANET--the precursor to today’s Internet. Engelbart received his bachelor’s degree in electrical engineering from Oregon State University in 1948, followed by an MS in 1953 and a Ph.D. in 1955 both from the University of California, Berkeley.

Punch card from a COBOL program
Jean Sammet

Jean E. Sammet was one of the first developers and researchers in programming languages. During the 1950’s - 1960’s she supervised the first scientific programming group for Sperry Gyroscope Co. and served as a key member of the original COBOL (COmmon Business-Oriented Language) committee at Sylvania Electric Products. She also taught one of the first graduate programming courses in the country at Adelphi College. After joining IBM in 1961, she developed and directed the first FORMAC (FORmula MAnipulation Compiler). This was the first widely used general language and system for manipulating nonnumeric algebraic expressions. In 1979 she began handling Ada activities for IBM’s Federal Systems Division. Ada is a structured, object-oriented high-level computer programming language, designed for large, long-lived applications, where reliability and efficiency are paramount. Jean has a B.A. from Mount Holyoke College and an M.A. from the University of Illinois, both in Mathematics. She received an honorary D.Sc. from Mount Holyoke (1978).

@ symbol
Ray Tomlinson
Ray Tomlinson

Have you ever considered that someone, at some point, was in a position to choose what symbol would be used separate the user from their location in an email address? That person, it turns out, was Ray Tomlinson, and in 1971 he chose "@". Tomlinson is credited with demonstrating the first email sent between computers on a network, and when asked what inspired him to make this selection he said, “Mostly because it seemed like a neat idea.”

After completing his Master’s degree at MIT in 1965, Ray joined the Information Sciences Division of Bolt Beranek and Newman Inc. of Cambridge, Massachusetts. Since then he has made many notable contributions to the world of network computing. He was a co-developer of the TENEX computer system that was popular in the earliest days of the Internet; he developed the packet radio protocols used in the earliest internetworking experiments; he created the first implementation of TCP; and he was the principle designer of the first workstation attached to the Internet.

Image credits