In this paper, we present an activity to introduce the idea of public-key cryptography and to make pre-service STEM teachers explore fundamental informatics and mathematical concepts and methods. We follow the Theory of Didactical Situations within the Didactical Engineering methodology (both widely used in mathematics education research) to design and analyse a didactical situation about asymmetric cryptography using graphs. Following the phases of Didactical Engineering, after the preliminary analysis of the content, the constraints and conditions of the teaching context, we conceived and analysed the situation a priori, with a particular focus on the milieu (the set of elements students can interact with) and on the choices for the didactical variables. We discuss their impact on the problem-solving strategies the participants need to elaborate to decrypt an encrypted message. We implemented our situation and collected qualitative data. We then analysed a posteriori the different strategies that participants used. The comparison of the a posteriori analysis with the a priori analysis showed the learning potential of the activity. To elaborate on different problem-solving strategies, the participants need to explore and understand several concepts and methods from mathematics, informatics, and the frontier of the two disciplines, also moving between different semiotic registers.