ECE 4331, Fall, 2009EncryptionSlide 3Encryption – cipher taxonomyTransposition MethodSubstitution MethodRotor MachineKeyPublic Key System - RSASlide 10Wireless Physical Layer SecurityQuantum CryptographyMission is really impossibleAutomatic Repeat-reQuest (ARQ)ARQError Correcting CodesTypes of Error Correcting CodesRepetition CodeParity CheckISDN NumberHammings SolutionError Detection AbilityHow it works: 3 dotsHamming DistanceAnother DotEven More DotsMulti-dimensional CodesCannon BallsExampleAnother Example: EncodingExample: Add noiseExample: Testing the messageExample: Repairing the messageCoding GainCoding Gain ExampleEncoder/Decoder of Linear CodeInterleavingARQ, FEC, HECECE 4331, Fall, 2009Zhu HanDepartment of Electrical and Computer EngineeringClass 21Nov.5th, 2009EncryptionEncryptionEncryption is a translation of data into a secret code. Encryption is the most effective way to achieve data security. To read an encrypted file, you must have access to a secret key that enables you to decrypt it. Unencrypted data is called plain text; encrypted data is referred to as cipher (text).Encryption can be used to ensure secrecy, but other techniques are still needed to make communications secure: authentication, authorization, and message integrity.EncryptionEncryptionMessage integrity - both parties will always wish to be confident that a message has not been altered during transmission. The encryption makes it difficult for a third party to read a message, but that third party may still be able to alter it in a useful way.Authentication is a way to ensure users are who they say they are - that the user who attempts to perform functions in a system is in fact the user who is authorized to do so.Authorization protects computer resources (data, files, programs, devices) by allowing those resources to be used by resource consumers having been granted authority to use them. Digital rights management etc.Encryption – cipher taxonomyEncryption – cipher taxonomyCIPHERSMODERNCIPHERSCLASSICALCIPHERSPUBLIC KEYPRIVATE KEYSUPERPOSITIONTRANSPOSITIONROTORMACHINESQuantumCIPHERSWireless PhysicalLayer SecurityTransposition MethodTransposition MethodDa Vinci’s codeEx.I am a studentI m s u e ta a t d nSubstitution MethodSubstitution MethodShift Cipher (Caesar’s Cipher)I CAME I SAW I CONQUEREDH BZLD H TZV H BNMPTDSDCJulius Caesar to communicate with his army Language, wind talkerRotor MachineRotor MachineThe primary component is a set of rotors, also termed wheels or dru ms, which are rotating disks with an array of electrical contacts on either side. The wiring between the contacts implements a fixed substitution of letters, scrambling them in some complex fashion. On its own, this would offer little security; however, after encrypting each letter, the rotors advance positions, changing the substitution. By this means, a rotor machine produces a complex polyalphabetic substitution cipher. German Enigma machine used during World War II for submarine. Movie U571, Italian JobKeyKeyPublic Key System - RSAPublic Key System - RSANamed after its inventors Ron Rivest, Adi Shamir and Len AdlemanBase on Number Theory y=ex (mod N) => x=??If the size of N is 100, it takes 100 billion years to decipher with 1GHz computer.Applications–Digital Signatures–Digital Cash: Movie, swordfish–Timestamping Services: Movie, entrapment –Election Movie, mercury risingEncryption – cipher taxonomyEncryption – cipher taxonomyHistorical pen and paper ciphers used in the past are sometimes known as classical ciphers. They include substitution ciphers and transposition ciphers.During the early 20th century, more sophisticated machines for encryption were used, rotor machines, which were more complex than previous schemes.Encryption methods can be divided into symmetric key algorithms and asymmetric key algorithms. In a symmetric key algorithm (DES, AES), the sender and receiver must have a shared key set up in advance and kept secret from all other parties; the sender uses this key for encryption, and the receiver uses the same key for decryption.In an asymmetric key algorithm (RSA), there are two separate keys: a public key is published and enables any sender to perform encryption, while a private key is kept secret by the receiver and enables him to perform decryption.Wireless Physical Layer Security Wireless Physical Layer Security Achieve zero information for the eavesdropper–Source transmits data rate of max(C1-C2,0) –The eavesdropper can decode zero information about the source.–Limit due to the locations of source, destination and relay–Can cooperation help to improveS DEC1C2Quantum CryptographyQuantum CryptographyUse physics law, if the signal is measured (eavesdropped), the receiver can always detected.Mission is really impossibleMission is really impossibleWhen you see it, the information has been already changedAutomatic Repeat-reQuest (ARQ)Automatic Repeat-reQuest (ARQ)Alice and Bob on their cell phones–Both Alice and Bob are talkingWhat if Alice couldn’t understand Bob?–Bob asks Alice to repeat what she saidWhat if Bob hasn’t heard Alice for a while?–Is Alice just being quiet?–Or, have Bob and Alice lost reception?–How long should Bob just keep on talking?–Maybe Alice should periodically say “uh huh”–… or Bob should ask “Can you hear me now?” ARQARQAcknowledgments from receiver–Positive: “okay” or “ACK”–Negative: “please repeat that” or “NACK”Timeout by the sender (“stop and wait”)–Don’t wait indefinitely without receiving some response–… whether a positive or a negative acknowledgmentRetransmission by the sender–After receiving a “NACK” from the receiver–After receiving no feedback from the receiverError Correcting CodesError Correcting CodesAdding redundancy to the original messageTo detect and correct errorsCrucial when it’s impossible to resend the message (interplanetary communications, storage..) and when the channel is very noisy (wireless communication)Information SourceMessageTransmitterNoise SourceDestinationMessageRecieverReceivedSignalSignalMessage = [1 1 1 1]Noise = [0 0 1 0]Message = [1 1 0 1]Types of Error Correcting CodesTypes of Error Correcting CodesRepetition CodeLinear Block Code, e.g. HammingCyclic Code, e.g. CRCBCH and RS CodeConvolutional Code–Tradition, Viterbi