5.12. Exercise: Encryption

5.12. Exercise: Encryption
	Chapter 5. Functions

[ fromfile: encryption-exercise.xml id: encryption-exercise ]

In Example 5.16 we declared but did not implement three operators for the Point3 class. Add implementations for these three operators and add tests to the client code.
In this exercise, you reuse the random() function from the <cstdlib> (Appendix B, "Standard Headers").
random() generates a pseudo-random integer in the range from 0 to RAND_MAX (commonly set to 2147483647).
Write a function
```
 int myRand(int min, int max); 
```
that returns a pseudo-random int in the range from min to max - 1.
Example 5.21. solution/encryption/crypto/randfunc.cpp
```
[ . . . . ]

int myRand(int min, int max) {
    return min + random() % (1 + max - min) ;
}
```
<include src="solution/encryption/crypto/randfunc.cpp" href="solution/encryption/crypto/randfunc.cpp" role="solution" mode="cpp" segid="myRand"/>

Write the function

QVector<int> randomPerm(int n, unsigned key);

that uses the myRand() function (seeded with key) to produce a permutation of the numbers 0, ... n.

Example 5.22. solution/encryption/crypto/randfunc.cpp

[ . . . . ]

void showVect(QVector<int> vec) {
    int vsize = vec.size();
    for (int i = 0; i < vsize; ++i)
        cout << vec[i] << "  ";
    cout << endl;   
}

 //Here is one way to obtain a random permutation of the numbers 0, ..., n :
 QVector<int> randomPerm(int n, unsigned key) {
     QVector<int> newperm(n) ; 
     newperm.fill(-1);
     srandom(key);
     int k;
     for (int i = 0; i < n; ++i) {
         while (1)  {
             k = myRand(0, n-1);
             if (newperm[k] != -1) continue;
             newperm[k] = i;
             break;
         }
     }
     return newperm;
 }

Encryption and privacy are becoming increasingly important. One way to think of encryption is that you start with a string of text that you pass to one or more transforming functions. The result of these transformations is a string of encrypted text that you can then transmit or store more safely. The recipient of the encrypted string then applies the inverses of the transforming functions to the string of encrypted text (i.e., decrypts it) and obtains a copy of the original string. The sender of the encrypted string must share some information with the recipient that permits the string to be decrypted (i.e., a key). The following exercises explore a few simple designs for the transforming functions. These exercises all exploit the fact that the sequence of values returned by random() is completely determined by the initial value (seed) and is, therefore, repeatable.
1. Write the function
```
 QString shift(const QString& text, unsigned key) ; 
```
  shift() uses the parameter key to set the random function's seed by calling srandom(). For each character ch in the given string, text, produce a shifted character by adding the next pseudo-random int to the code for ch. The shifted character is then put in the corresponding place in the new string. When all the characters of text have been processed, shift() returns the new string.
  When you add a random int to the code for a character you must do the addition "mod n" where n is the number of characters in the underlying character set that is being used. For this exercise, you can assume that you are working with the ASCII character set, which has 128 characters.
  Example 5.23. solution/encryption/crypto/randfunc.cpp
  [ . . . . ] /* shift() works with the QChars of the given QString */ QString shift(const QString& text, unsigned key) { const ushort P(127); // The size of the ASCII char set. srandom(key); QString cryptstr; ushort ccode, shiftcode; int rnd; for (int i = 0; i < text.length(); ++i) { rnd = random(); ccode = text[i].unicode(); shiftcode = (ccode + rnd) % P ; cryptstr[i] = QChar(shiftcode) ; } return cryptstr; }
  <include src="solution/encryption/crypto/randfunc.cpp" href="solution/encryption/crypto/randfunc.cpp" role="solution" mode="cpp" segid="shift"/>
2. The next function to write is
```
 QString unshift(const QString& cryptext, unsigned key); 
```
  This function reverses the process described in the previous exercise.
  Example 5.24. solution/encryption/crypto/randfunc.cpp
  [ . . . . ] QString unshift(const QString& text, unsigned key) { const ushort P(127); srandom(key); QString cryptstr; int temp; ushort ccode, uscode; int rnd; for (int i = 0; i < text.length(); ++i) { rnd = random(); ccode = text[i].unicode(); temp = (ccode - rnd) % P ; // may be negative temp = (temp + P) % P; // make sure it's positive uscode = temp; // convert back to ushort cryptstr[i] = QChar(uscode) ; } return cryptstr; }
  <include src="solution/encryption/crypto/randfunc.cpp" href="solution/encryption/crypto/randfunc.cpp" role="solution" mode="cpp" segid="unshift"/>
3. Write code to test your shift() and unshift() functions.
4. Another approach to encryption (which can be combined with the approach described above) is to permute (change the order of) the characters of the given string. Write the function
```
 QString permute(const QString& text, unsigned key); 
```
  that uses the randomPerm() function to generate a permutation of the characters of the original string, text.
  Example 5.25. solution/encryption/crypto/randfunc.cpp
  [ . . . . ] QString permute(const QString& text, unsigned key) { int slen = text.length(); QVector<int> perm = randomPerm(slen, key); QString scrstr; for (int i = 0; i < slen; ++i) scrstr += text.at(perm[i]); return scrstr; }
  <include src="solution/encryption/crypto/randfunc.cpp" href="solution/encryption/crypto/randfunc.cpp" role="solution" mode="cpp" segid="permute"/>
5. Write the function
```
 QString unpermute(const QString& scrtext, unsigned key); 
```
  that reverses the action of the permute() function described above.
  Example 5.26. solution/encryption/crypto/randfunc.cpp
  [ . . . . ] QString unpermute(const QString& text, unsigned key) { int slen = text.length(); QVector<int> perm = randomPerm(slen, key); QString uscrstr; for (int i = 0; i < slen; ++i) uscrstr[perm[i]] = text[i]; return uscrstr; }
  <include src="solution/encryption/crypto/randfunc.cpp" href="solution/encryption/crypto/randfunc.cpp" role="solution" mode="cpp" segid="unpermute"/>
6. Write code to test your permute() and unpermute() functions.
7. Write code to test shift() and permute() being applied to the same string, followed by unpermute() and unshift().
  Example 5.27. solution/encryption/crypto/randfunc.cpp
  [ . . . . ] int main() { QString str1 ("This is a sample string"), str2; cout << "Original string: " << str1 << endl; str2 = shift(str1, 1234); cout << "Shifted string: " << str2 << endl; cout << "Recovered string: " << unshift(str2, 1234) << endl; const int vsize(20); QVector<int> vec(vsize); vec = randomPerm(vsize, 1234); showVect(vec); str2 = permute(str1, 1234); cout << "Original string permuted: " << str2 << endl; cout << "Unpermuted string: " << unpermute(str2, 1234) << endl; QString str3 = shift(str2, 1234); cout << "Shifted, permuted string: " << str3 << endl; cout << "Recovered string: " << unpermute(unshift(str3, 1234), 1234) << endl; }
  <include src="solution/encryption/crypto/randfunc.cpp" href="solution/encryption/crypto/randfunc.cpp" role="solution" mode="cpp" segid="testcode"/>

Implement a Crypto class that encapsulates the functions from the preceding exercises. You can use the UML diagram in Figure 5.4 to get you started.

Figure 5.4. Crypto Class

m_OpSequence is a QString consisting of the characters 'p' and 's' that represent permute() and shift(). The encrypt() function applies those functions to the given string in the order that they appear in the m_OpSequence string.

Example 5.28 contains some code to test your class.

Example 5.28. src/functions/crypto-client.cpp

#include <QTextStream>
#include "crypto.h"

int main()  {
   QTextStream cout(stdout);
   QString str1 ("asdfghjkl;QWERTYUIOP{}}|123456&*()_+zxcvnm,,, ./?"), 
           str2;
   cout << "Original string: " << str1 << endl;
   cout << "length: " << str1.length() << endl;
   QString seqstr("pspsp");
   ushort key(12579);
   Crypto crypt(key, seqstr);
   str2 = crypt.encrypt(str1);
   cout << "Encrypted string: " << str2 << endl;
   cout << "Recovered string: " << crypt.decrypt(str2) << endl;
}

Example 5.29. solution/encryption/cryptoclass/crypto.cpp

#include "crypto.h"
#include <stdlib.h>  // for random()

Crypto::Crypto(ushort key, QString opseq, ushort charsetsiz) 
: m_Key(key), m_OpSequence(opseq), m_CharSetSize(charsetsiz) { }

QString Crypto::encrypt(const QString& str) {
    randomPerm(str.length());
    QString oldstr(str), newstr;
    for (ushort i = 0; i < m_OpSequence.length(); ++i) {
        if (m_OpSequence[i] == 's')
            newstr = shift(oldstr);
        else
            newstr = permute(oldstr);
        oldstr = newstr;
    }
    return newstr;
}

QString Crypto::decrypt(const QString& str) {
    randomPerm(str.length());
    QString oldstr(str), newstr;
    for (ushort i = m_OpSequence.length(); i > 0;  --i) {
        if (m_OpSequence[i -1] == 's')
            newstr = unshift(oldstr);
        else
            newstr = unpermute(oldstr);
        oldstr = newstr;
    }
    return newstr;  
}


/* shift() works with the QChars of the given QString */
QString Crypto::shift(const QString& text)  const{
    srandom(m_Key);
    const ushort P(m_CharSetSize);
    QString cryptstr;
    ushort ccode, shiftcode;
    int rnd;
    for (int i = 0; i < text.length(); ++i) {
        rnd = limitedRand(m_CharSetSize);
        ccode = text[i].unicode();
        shiftcode = (ccode + rnd) % P ;
        cryptstr[i] = QChar(shiftcode) ;
    }
    return cryptstr;
}

QString Crypto::unshift(const QString& text)  const{
   srandom(m_Key);
   const ushort P(m_CharSetSize);
   QString cryptstr;
   ushort ccode, shiftcode;
   int rnd;
   for (int i = 0; i < text.length(); ++i) {
      rnd = limitedRand(m_CharSetSize);
      ccode = text[i].unicode();
      shiftcode = ((ccode + P) - rnd) % P ;  // make sure it's positive
      cryptstr[i] = QChar(shiftcode) ;
   }
   return cryptstr;
}

int Crypto::limitedRand(int max) {
   return random() % max ;
}

void sequenceFill(QVector<int>& vec) {
   for (int i = 0; i < vec.size(); ++i) 
       vec[i] = i;
}

void swap(int& x, int& y) {
    int temp;
    temp = x;
    x = y;
    y = temp;
}

void Crypto::randomPerm(int n)  {
    const int numswaps(2 * n);
     m_Perm.clear(); 
     m_Perm.resize(n);
     sequenceFill(m_Perm);
     srandom(m_Key);
     int j, k;
     for (int i = 0; i < numswaps; ++i) {
             j = limitedRand(n);
             k = limitedRand(n);
             swap(m_Perm[j], m_Perm[k]);
     }
}

QString Crypto::permute(const QString& text) {
    int slen = text.length();
    QString scrstr;
    for (int i = 0; i < slen; ++i) 
        scrstr += text.at(m_Perm[i]);
    return scrstr;
}

QString Crypto::unpermute(const QString& text) {
    int slen = text.length();
    QString uscrstr;
    for (int i = 0; i < slen; ++i) 
        uscrstr[m_Perm[i]] = text[i];
    return uscrstr;
 }

Now that you have developed a Crypto class for encrypting and decrypting strings, use that class for managing the passwords for users of some system.

Figure 5.5. User Manager UML

In addition to the Crypto member, the UserManager class also needs members to hold, for each user, the userid and encrypted password. ^[42]

All of the member functions are "silent" (i.e., no interaction with the user). User interactions take place only in the client code.

The constructor instantiates the Crypto member.

Each of the three bool functions returns true if the operation is successful.

loadList() and saveList() both access a file named pwfile. They each return the number of users.

Write the class definition for UserManager.

Example 5.30. solution/encryption/usermanager/usermanager.h

#ifndef USER_MANAGER_H_
#define USER_MANAGER_H_

#include "crypto.h"
#include <QStringList>

class UserManager {
  public:
    UserManager(ushort cryptoKey, QString opseq, ushort charsiz = 128);
    bool changePW(QString userid, QString oldPW, QString newPW);
    bool addUser(QString userid, QString pw);
    bool checkUser(QString userid, QString pw);
    int saveList() const;
    int loadList();
    void listUsers() ;  /*For debugging purposes.*/
  private:
    Crypto m_Cryptor;
    QStringList m_useridList; 
    QStringList m_pwList;  
    int findUser(QString userid, const QString& pw) ;
};

#endif

	stores userids
	stores encrypted passwords

Write implementations for all of the methods listed in the UML diagram for the UserManager.

Example 5.31. solution/encryption/usermanager/usermanager.cpp

#include "usermanager.h"
#include <QFile>
#include <QTextStream>

UserManager::
UserManager(ushort cryptoKey, QString opseq, 
            ushort charsiz)  :    
    m_Cryptor(cryptoKey, opseq, charsiz) { }

int UserManager::
findUser(QString userid, const QString& pw) {
    int indx, size(m_useridList.size());
    QString cryptpw(m_Cryptor.encrypt(pw));
    for (indx = 0; indx < size; ++ indx) 
        if (userid == m_useridList.at(indx) && 
           cryptpw == m_pwList.at(indx)) 
            return indx;
    return -1;
}

bool UserManager::
changePW(QString userid, QString oldPW, 
         QString newPW)  {
    int indx = findUser(userid,  oldPW);
    if (indx == -1) return false;
    m_pwList[indx] = m_Cryptor.encrypt(newPW);
    return true;
}
    
bool UserManager::
addUser(QString userid, QString pw) {
    // First make sure userid does not already exist.
    if (findUser(userid, pw) != -1) return false;
    m_useridList.append(userid);
    m_pwList.append(m_Cryptor.encrypt(pw));
    return true;
}

bool UserManager::
checkUser(QString userid, QString pw) {
    int indx = findUser(userid, pw);
    return indx != -1;
}

int UserManager::
saveList() const {
    QString separator("***ZONE***");
    QString userids(m_useridList.join(separator));
    QString passwords(m_pwList.join(separator));
    QFile outfile("pwfile");
    if (outfile.open(QFile::WriteOnly)) {
        QTextStream of(&outfile);
        of << userids << '\n' ;
        of << passwords << endl;
        outfile.close();
        return m_useridList.size();
    }
    else
        return 0;
}

int UserManager::
loadList() {
    QString separator("***ZONE***");
    QString userids;
    QString passwords;
    QFile infile("pwfile");
    if (infile.open(QFile::ReadOnly)) {
        QTextStream inf(&infile);
        userids = inf.readLine();
        passwords = inf.readLine();
        m_useridList.clear();
        m_useridList = userids.split(separator);
        m_pwList.clear();
        m_pwList = passwords.split(separator);
        if (m_useridList.size() == m_pwList.size())
            return m_useridList.size();
        return 0;
    }
    else
        return 0;
}

void UserManager::   
listUsers()  {
    QTextStream cout(stdout, QIODevice::WriteOnly);
    QTextStream cin(stdin, QIODevice::ReadOnly);
    int count(m_useridList.size());
    cout << "userid\tpassword\n" ;
    for (int i=0; i < count; ++i)
        cout << m_useridList[i] << '\t' 
                << m_Cryptor.decrypt(m_pwList[i]) << '\n';
    cout << endl;
}

	= 128
	for debugging purposes

Write client code to thoroughly test UserManager.

Example 5.32. solution/encryption/usermanager/usermanager-test.cpp

#include "usermanager.h"
#include <QTextStream>
QTextStream cout(stdout, QIODevice::WriteOnly);
QTextStream cin(stdin, QIODevice::ReadOnly);
enum  Choices {LOAD = 1, ADD, CHANGE, CHECK, SAVE, LIST, QUIT}; 

Choices menu() {
    QString str;
    int n;
    do {
        cout << LOAD      << "\tLoad User/PW list from file\n"
                << ADD    << "\tAdd users to the list\n"
                << CHANGE << "\tChange a user's password\n"
                << CHECK  << "\tCheck a user's password\n"
                << SAVE   << "\tSave User/PW list to file\n"
                << LIST   << "\tShow all userids and passwords\n"
                << QUIT   << "\tQuit the program\n"
                << "Your choice: " << flush;
        str = cin.readLine();
        n = str.toInt();
    } while ( n < LOAD || n > QUIT);
    return static_cast<Choices>(n); 
}

QString promptUserid() {
    QString userid;
    int len;
    const int MINLEN(6), UMAXLEN(8);
    while (1) {
        cout << "User ID (" << MINLEN << " to " 
                << UMAXLEN << " chars - no spaces): " 
                << flush ;
         userid = cin.readLine();
         len = userid.length();
         if (len < MINLEN || len > UMAXLEN ||
             userid.contains(' ')) {
              cout << "Invalid userid!" << endl;
              continue;
         }
         return userid;
    } 
}

QString promptPW(bool repeat = true) {
    QString  pw1, pw2;
    int len;
    const int MINLEN(6), PMAXLEN(12);
    while (1) {
         cout << "Password (" << MINLEN << " to " 
                  << PMAXLEN << " chars): " << flush;
         pw1 = cin.readLine();
         len = pw1.length();
         if (len < MINLEN || len > PMAXLEN) {
             cout << "Invalid password!" << endl;
             continue;
         }
         if (repeat) {
             cout << "Retype password: " << flush;
             pw2 = cin.readLine();
             if (pw1 != pw2) {
                 cout << "Passwords do not match!" << endl;
                 continue;
             }
         }
         return pw1;
    }
}

void addUsers(UserManager& um) {
    QString userid, pw, ans;
    do {
        userid = promptUserid();
        pw = promptPW();
        cout << "Userid " << userid ;
        if (not um.addUser(userid, pw)) 
            cout << " already exists. \n" ;
        else
            cout << " added to list. \n" ;
        cout << "Add another user (y/n)? " << flush;
        ans = cin.readLine().toUpper();
    } while (ans[0] == 'Y');
}

void changePassword(UserManager& um) {
    QString userid(promptUserid());
    cout << "Current password ..." << endl;
    QString oldpw(promptPW(false));
    cout << "New password ..." << endl;
    QString newpw(promptPW());
    um.changePW(userid, oldpw, newpw);
}

void checkUser(UserManager& uw) {
    QString userid(promptUserid());
    QString pw(promptPW(false));
    if (uw.checkUser(userid, pw))
        cout << "User " << userid << " can login." <<endl;
    else
        cout << "Invalid userid or password." << endl;
}


int main() {
    QString seqstr("pspsps");
    ushort key(13579);
    UserManager um(key, seqstr);
    while (1) {
        switch (menu()) {
           case LOAD:  
                cout << "Reading from file ...\n"
                        << um.loadList() << " loaded to list"
                         << endl;
                break;
            case ADD:
                cout << "Adding users to the list ..." << endl;
                addUsers(um);
                break;
            case SAVE:
                cout << "Saving changes ...\n"
                       << um.saveList() << " users in file" << endl;
                break;
            case CHANGE:
                cout << "Changing password ..." << endl;
                changePassword(um);
                break;
            case CHECK:
                cout << "Checking a userid/pw combo ..." << endl;
                checkUser(um);
                break;
            case LIST:
                cout << "Listing users and passwords ...\n";
                um.listUsers();
                break;
            case QUIT:
                cout << "Exiting the program ..." << endl;
                return 0;
           default:
                cout << "Invalid choice! " << endl;
        }
    }
}

	Enums are discussed in Chap. 19.
	Casts are discussed in Chap. 19

The topic of encryption is visited again in Section 17.1.4 which introduces a Qt class that does cryptographic hashing.

^[42] QMap would be a good choice if you want to read ahead a bit. Section 6.8


5.11. Functions with Variable-Length Argument Lists		5.13. Review Questions