Many security primitives are based on difficult mathematical problems. The use of hard AI problems for security is emerging as a new exciting paradigm, but has been under-explored. CaRP is both a Captcha and a graphical password scheme. CaRP addresses a number of security issues together, such as online divination attacks, retransmission attacks and, if combined with dual-view technologies, surfing attacks on the shoulder. In particular, a CaRP password can only be found probabilistically by automatic online guessing attacks, even if the password is in the search set. CaRP also offers a novel approach to addressing the well-known image hotspot problem in popular graphical password systems, such as PassPoints, which often leads to weak password options. CaRP is not a panacea but offers reasonable security and usability and seems to fit well with some practical applications to improve online security.